Recursive scan for ACLs on directories with C++

Question

I was curious about something. I'm writing a piece of code with C++ that needs to scan ACL permissions on subfolders of a specific folder and find those that differ from the ACL permissions of the first folder. To do that I recursively check all folders within the folder, using FindFirstFile and FindNextFile and then check ACL permissions by calling GetNamedSecurityInfo on each subfolder found.

This method works, except that it works very slow, especially when scanning network shares. I know that the tool called accesschk can do the same thing, but when I run it recursively on the same folder (with -dsqvli switches) it returns the result way quicker than my procedure I described above.

So I was wondering how can I speed up this ACL permissions look up process?

My first thought was to use inheritance on ACEs, I'm just not sure how to implement it...

EDIT 2: Thanks @arx for suggestions. This ACL/ACE stuff is very poorly documented. The code he posted below worked for me. Note that my original code for checking ACL inheritance did not produce reliable results due to the reason's @arx outlined below in his post.

Answer 1

Some further information from the comments:

The application determines the SID of a user whose access rights are being checked.

Having called GetNamedSecurityInfo on each directory, the application calls GetEffectiveRightsFromAcl with the SID of the user. It is the latter call that is taking most of the time.

GetEffectiveRightsFromAcl checks the ACL against the user's SID and the SIDs of any groups the user is a member of. It is likely slow because determining a user's groups requires a round trip to the domain controller.

There are two possible fixes and a dead end:

Emulate GetEffectiveRightsFromAcl

Outside the loop, determine the SID of the user and the SIDs of the user's groups. (TODO: Check if nested groups are handled automatically, or if they must be resolved recursively.)

To determine the effective rights for an ACL:

1. Use an ACCESS_MASK (actually a DWORD) to represent the rights mask. Initialize it to zero.
2. Process the ACEs in the ACL in reverse order. This ensures that earlier ACEs take precedence.
3. If an ACE refers to any of the previously determined SIDs then, for access-allowed ACEs OR the ACE's mask with your rights mask and for access-denied ACEs mask off the ACE's mask from your rights mask.

Once you've processed all the ACEs your rights mask holds the answer.

Skip Inherited ACLs

In many directory hierarchies most or all of the files and directories will inherit their permissions from their parents. However, this doesn't help. Inherited ACLs may not be active on the parent, so the effective rights of the children won't match the effective rights of the parent. So an ACL still has to be checked even if it inherited.

Cache the result of GetEffectiveRightsFromAcl

Simply create a map from ACLs to effective rights masks. To do this you need a way of comparing ACLs. You can't just compare entire ACLs using memcmp because ACL.AclSize includes the size of extra padding. Instead, compare the number of ACEs, and if they are the same compare the individual ACEs using memcmp.

I tried this on my Program Files directory. Scanning the whole directory structure required 6 calls to GetEffectiveRightsFromAcl. The remaining 2,708 directories were resolved from the cache so it was much faster.

The following implements a cached version of GetEffectiveRightsFromAcl. Note that error-handling is lacking, and it never frees the PACLs it puts in the map.

// Compare two access-control lists.
// Return <0 if acl1<acl2, 0 if acl1==acl2 and >0 if acl1>acl2.
// The ordering is arbitrary but consistent.
int aclcmp(PACL acl1, PACL acl2)
{
    // First compare by number of ACEs
    int c = acl1->AceCount - acl2->AceCount;
    if (c)
        return c;

    // We have the same number of ACEs, so compare each ACE
    int aceCount = acl1->AceCount;
    for (int aceIndex = 0; aceIndex != aceCount; ++aceIndex)
    {
        // Get the ACEs
        PACE_HEADER ace1;
        PACE_HEADER ace2;
        GetAce(acl1, aceIndex, (LPVOID*)&ace1);
        GetAce(acl2, aceIndex, (LPVOID*)&ace2);
        // Compare the ACE sizes
        c = ace1->AceSize - ace2->AceSize;
        if (c)
            return c;

        // Compare the ACE content
        c = memcmp(ace1, ace2, ace1->AceSize);
        if (c)
            return c;
    }

    return 0;
}

// Less-than operator for pointers to ACLs
class ComparePAcl
{
public:
    bool operator()(const PACL& acl1, const PACL& acl2) const
    {
        return aclcmp(acl1, acl2) < 0;
    }
};

// Map from pointers-to-ACLs to access masks
typedef std::map<PACL, ACCESS_MASK, ComparePAcl> AclToAccessMask;
AclToAccessMask aclToAccessMask;

// Just to check how the cache performs
DWORD foundCount = 0;
DWORD notFoundCount = 0;

// Same as GetEffectiveRightsFromAcl but caches results.
// Note that this must be called with the same trustee to get meaningful results.
DWORD CachedGetEffectiveRightsFromAcl(PACL pacl, PTRUSTEE pTrustee, PACCESS_MASK pAccessRights)
{
    AclToAccessMask::const_iterator it = aclToAccessMask.find(pacl);
    if (it != aclToAccessMask.end())
    {
        // The ACL is in the cache
        ++foundCount;
        *pAccessRights = it->second;
    }
    else
    {
        // The ACL is not in the cache
        ++notFoundCount;
        DWORD rc = GetEffectiveRightsFromAcl(pacl, pTrustee, pAccessRights);
        if (rc != ERROR_SUCCESS)
            return rc;
        // TODO: Clean up copies of ACLs afterwards
        PACL aclcopy = (PACL)malloc(pacl->AclSize);
        memcpy(aclcopy, pacl, pacl->AclSize);
        aclToAccessMask.insert(AclToAccessMask::value_type(aclcopy, *pAccessRights));
    }

    return ERROR_SUCCESS;
}