June, 2007

  • The Old New Thing

    Why does canonical order for ACEs put deny ACEs ahead of allow ACEs?


    So-called canonical order for ACEs in an access control list places deny ACEs ahead of allow ACEs. Why is this the canonical order?

    Because it gives results that are sensible.

    The algorithm for determining whether a user has access to an object protected by an ACL is as follows:

    let access-still-needed = access-requested
    for each ACE in the ACL that applies to the user (in order)
        if it is a deny ACE:
            if (access-still-needed & ace-mask) return access-denied
        if it is an allow ACE:
            access-still-needed &= ~ace-mask
    end for loop
    if access-still-needed != 0 return access-denied
    return access-granted

    In words, we go through the ACEs in the ACL in the order they appear, paying attention only to the ones that apply to the user, i.e. the ones whose SIDs are present in the user's token. If a permission is being denied, and the user is still looking for that permission, then access is denied. If a permission is being granted, then those permissions are subtracted from the permissions the user is still looking for. If, at the end of the day, all the permissions the user requests have been granted, then access is granted.

    The key detail in the above algorithm is that deny ACEs apply to permissions not yet granted and not to the original set of permissions requested. If you deny write, but an earlier ACE grants it, then the deny has no effect.

    Let's look at what happens if we apply this algorithm to an ACL that is not in canonical order. Our ACL is as follows:

    • Grant write access to Alice.
    • Deny read and write access to Users.
    • Grant read access to Users.

    Let's say that Alice wants write access. We start with access-still-needed = write, and the first ACE grants it, leaving access-still-needed equal to zero. The second ACE denies read and write, but Alice already got write access thanks to the first rule, and she never asked for read access, so this deny ACE has no effect. The third ACE also has no effect since Alice wasn't looking for read access. Result: Alice gets write access.

    On the other hand, suppose Alice wants read access. The first ACE has no effect, since Alice isn't interested in write access. The second ACE then denies access since Alice is being denied read access which she hasn't gotten yet. Alice's request is rejected without even looking at the third ACE.

    Notice that if the ACEs are not canonically-ordered, you can't use a simple rule like "deny ACEs take priority over allow ACEs". The rule is "Well, you have to go through each ACE one by one, and you get access if you get all the things you want before somebody denies them." It sort of turns into a game show.

    Since graphical ACL editors typically don't show the order of the ACEs, some sort of canonical order needs to be established so that you don't run afoul of this "order of operations" problem. Notice that in the algorithm above, you can swap two adjacent allow ACEs and two adjacent deny ACEs without affecting the result, but you cannot swap the positions of an allow and a deny ACE. Therefore, the canonical ordering must either be "all deny ACEs come before all allow ACEs" or "all allow ACEs come before all deny ACEs".

    Note, however, that if you choose to have all allow ACEs come before all deny ACEs, then you don't need deny ACEs at all! If you look at the algorithm above, if there is no ACE that mentions the permission you want, then access is denied. The deny ACEs don't add anything to the picture:

    // assuming that all allow ACEs come before all deny ACEs
    let access-still-needed = access-requested
    for each allow ACE in the ACL that applies to the user (in order)
        access-still-needed &= ~ace-mask
    end for loop
    for each deny ACE in the ACL that applies to the user (in order)
        if (access-still-needed & ace-mask) return access-denied
    end for loop
    if access-still-needed != 0 return access-denied
    return access-granted

    Notice that once you make it out of the first "for" loop, the return value is going to be access-denied if access-still-needed is nonzero. All the deny ACEs give you is another way to say "no". But you were going to say "no" anyway.

    Therefore, for deny ACEs to be meaningful, the canonical ordering should place them ahead of allow ACEs. That way, you get three tiers of permission instead of just two:

    • If there is a deny ACE, then it is denied.
    • If there is no deny ACE but there is an allow ACE, then it is allowed.
    • If there is neither a deny ACE or an allow ACE, then it is denied.

    Postscript: Our sample non-canonical ACL above can easily be converted to an equivalent canonical one:

    • Grant write access to Alice.

    Why does this work?

    Well, first notice that the second rule ("Deny read and write access to Users") completely overrides the third rule ("Grant read access to Users"), since any attempt by the third rule to grant read access to Users will be thwarted by the second rule, which denies it.

    But the second rule itself is unnecessary. We are taking advantage of the test outside the loop in the access algorithm: if access-still-needed != 0 return access-denied. This rule means that the default for all access mode is to deny. Therefore, you don't need to deny anything explicitly unless you have a broader rule later that grants it. (If you have a more narrow rule later that grants it, then that narrower rule is pointless, as we saw in the previous paragraph.) In other words, there's no point denying read and write to Users since merely not saying anything is equivalent to a denial.

  • The Old New Thing

    The meaning of a red traffic light is open to interpretation


    It seems a sure-fire way to get a lot of good comments is to write about traffic lights or crazy driving, so I'm going to combine the two and write about crazy driving at traffic lights. Then my comments will set a new record.

    My friend The Knitty Professor told me about the time the sister of one of her friends came to visit from another country. The sister was driving through the streets of Boston with my friend among the passengers, and she drove straight through a red light.

    After my friend checked that she was still alive, she pointed out politely that the traffic light they had just driven through was in fact red.

    "That's okay," the sister replied. "I'll stop at the next one."

    Update: See a comment from the Knitty Professor herself for additional clarification.

  • The Old New Thing

    How do I inflate a bicycle tire with a potato?


    I see this all the time.

    People have a problem and have already decided what technology they're going to use to solve it, and then they hit a roadblock: The technology they picked is unsuited to the problem!

    How do I put my laptop into standby mode from VBScript?
    How do I change the user's mouse acceleration from a batch file? I changed the registry values but it doesn't take effect immediately.

    The functionality you seek is implemented in native code via Win32. At the end of the day, the solution involves calling SetSystemPowerState or SystemParametersInfo(SPI_SETMOUSE), since those are the functions that actually do the work.

    There's no law that forbids writing programs in C or C++, particularly since that's the target language for the native bits of Win32. Go ahead, write that program, and then call it from your batch file.

    Now, it's possible that you can get somebody else to play middle-man for you. For example, if you wanted to shut down the computer, you can get the shutdown.exe program to help out. And if you had chosen wisely, the technology you already decided upon may wrap the Win32 functionality inside a helper function or class, or it may provide a way of calling into native Win32 code. For example, your Visual Basic program could just call SetSystemPowerState via a platform invoke:

    Public Shared Function SetSystemPowerState(_
          fSuspend As Boolean, _
          fForce As Boolean) As Boolean
    SetSystemPowerState(True, False)

    (Note: I don't speak Visual Basic, so I may have gotten the details wrong, but I hope you get the idea.)

  • The Old New Thing

    How not to prepare for the STP (2007 edition)


    I signed up for the annual Seattle-to-Portland bike ride, known to Seattle-area bicycling dorks as STP. My bicycle riding is mostly just commuting to and from work, nothing even approaching the 200-mile trek that STP entails, but one of my friends who recently started bicycle-commuting inspired our little bicycle commuting group to sign up.

    One of my colleagues rode the STP last year, and when he returned, I asked him how it went. He conceded that he was riding with a group that wanted to go faster than he was prepared to ride, and the ride was not quite as enjoyable as it could have been.

    "I should've trained better."

    Oh? What was your training?

    "I sat around and drank beer."

  • The Old New Thing

    Email tip: Lay off the massive email signatures


    All too often I see email like this:

    From: X

    Is there a way to turn off Q?


    Support Professional
    Microsoft Product Support Services
    Tel: +123 456 7890 Extension 1234

    Email: X@microsoft.com

    In case I am unavailable and you need urgent assistance, you can contact the following people:

    My Backup: Y, Phone: +123 456 7890 Extension 1235 or Email: Y@microsoft.com

    My Manager: Z, Phone: +123 456 7890 Extension 1236 or Email: Z@microsoft.com

    Note: If you are a customer of Microsoft, Please refer to the terms and conditions which cover the provision of support and consulting services to you/your organization. If you are not a corresponding in the course of, or in connection with a Microsoft contract or program with its own terms and conditions, Please note that no liability is accepted by Microsoft for the contents of this email.

    Not only is your email signature is longer than your message, it's also more colorful and makes greater use of boldface, so the reader's eye is going to be attracted to the signature and miss your question entirely. (This is actually a rather subdued version. I've seen much worse, with animated images in the signature.)

    Don't let your message get lost in the medium. The email signature should not draw attention away from your message. What's more, it shouldn't convey information that the reader doesn't need to know. First of all, we already know your name and email address since it's in the message header. And since this message was sent internally, we can easily look up your job title, division, telephone number, and manager's name, and the huge disclaimer at the bottom is completely unnecessary since the message is internal and wasn't sent to any of your support customers.

    The only information in the signature that we didn't already know (or couldn't already find out) is your backup, and I suspect this question could have gotten by without even that.


    Some time ago, I had a hobby of collecting hideous email signatures and organized nearly 200 of them into an online "email signature museum". If things get slow, I could trot those out.

  • The Old New Thing

    It's official: The logo for the London 2012 Olympic Games is hideously ugly


    Yesterday, the organizers of the London 2012 Olympic Games unveiled their official logo, and it's officially hideous. They paid £400,000 for that? As one of my friends put it, it looks like a bunch of old people tried to imagine something that would appeal to young people. Unfortunately, they forgot that today's young people don't live in the 1980's.

  • The Old New Thing

    Compatibility constraints of the water cooler


    One of the things you learn when dealing with compatibility is that every single external detail is a potential compatibility constraint.

    A few years ago, the water coolers in the buildings were replaced. I have no idea why. Maybe the new water cooler company put in a lower bid. Who knows? All I know is that I like the newer ones less, and I'm not the only one.

    The water cooler has three spouts: one for hot water, one for room-temperature water, and one for cold water. (Okay, so it's also a water heater as well as a water cooler.) The old machine positioned the spouts close enough together that you could fit a cup beneath the last two spouts (room-temperature and cold). This meant that you could push both levers to dispense water into your cup. Now, the result was "somewhat cool" water, but the important thing was that it filled your cup in half the time!

    Hot Temp Cold
      |   |   |
      v   v   v
         |.   .|

    The new water coolers has the same three spouts, but they are positioned just a tiny bit further apart, just far apart enough that you can't use the "double-barrel" trick any more.

    Hot  Temp  Cold
      |    |    |
      v    v    v
          |.    |.
          |.cup |.dribble

    The new water cooler is subtly incompatible with the old one, in a manner that is not part of the specification but rather is merely a convenient side-effect of the implementation.

  • The Old New Thing

    Death at a Funeral, Cashback, and Tell No One


    Another installment in Raymond's short reviews of SIFF movies he's seen recently.

    4 stars out of 5 Death at a Funeral: The family funeral gets off to a bad start when the funeral home delivers the wrong body, and it's the only mishap that actually gets fixed without further incident. Everything else goes horribly wrong, and then when you thought it couldn't get any worse, it gets worse. Hilarious if you're willing to laugh at uncomfortable situations, a disaster spiraling out of control, men behaving badly, gross-out humor, accidental consumption of hallucinogens, an old man with a filthy mouth, and lots of other stuff that will earn you an R rating. I give it a 4 out of 5.

    4 stars out of 5 Cashback, a full-length version of the 2006 Academy-Award-nominated short of the same name: Everybody who has worked an hourly job knows that staring at the clock just makes time feel like it's standing still. Ben manages to turn this feeling into reality while working the night shift at a grocery store, giving him opportunities to escape from his crazy boss, his even crazier coworkers, and to pine after the cute cashier girl. A very sweet story lurks behind the insanity. I give it a 4 out of 5.

    3 stars out of 5 Tell No One: A man becomes a suspect for the murder of his wife eight years earlier. The opening of the movie is uncomfortably tense because you know the wife is going to die and it's just a matter of waiting for it to happen. The screws slowly tighten on Alexandre Beck until he finds himself running for his life. And, believe or not, that's when the tension eases up. (Thankfully, in my case. I don't handle suspense well.) There are some funny moments during his period in hiding, trying to figure out what's really going on, and the tension actually drops as more and more pieces of the puzzle start to emerge. I was kind of disappointed, however, by the ending, (spoiler: highlight with mouse to read) which is a pretty standard "hero held a gunpoint while the villain explains everything that happened". There's a little twist, but not enough to vindicate it. Even so, I give it a 3 out of 5.


    5 stars out of 5 Would pay money to see again by myself.
    4 stars out of 5 Would see again if it were free or if seeing it with others.
    3 stars out of 5 Would recommend to others.
    2 stars out of 5 Okay, but wouldn't recommend to someone not already interested.
    1 star out of 5 Would advise against.
    0 stars out of 5 Waste of my time.

    Note: The rating scheme has been revised since this article was originally posted.

  • The Old New Thing

    Choosing a provocative debug signature


    Back in Windows 95, there was an elusive heap corruption bug in the graphics engine, and after a lot of analysis, the graphics folks were convinced that the corruption was coming from outside their component, and they had a pretty good idea who the corruptor was, but they needed proof.

    One of the standard techniques of narrowing down the source of a problem like this is to put a signature value in the object and validating the signature on entry to every function that uses that object as well as on exit. If you find that the signature was valid on entry but is corrupted on exit, then your function corrupted it. Conversely, if it was valid on exit but is invalid on a subsequent entry, then somebody else corrupted it. At least that's the theory.

    The developer who was responsible for investigating the bug decided to use this "signature value" technique. It is often the case that, for throwaway temporary signatures like this, you will use your own initials as the signature value. This is partly egotism but mostly just lack of creativity. But this particular developer had a better idea. Since he had a pretty good idea which component was corrupting the memory, he used not his own initials, but the initials of the developer responsible for the component he thought was the corruptor! That way, when that developer's component corrupted the signature, it'd just be corrupting his own initials.

    Of course, when the developer of the suspect component saw this check-in, he felt kind of insulted. After all, his friend just accused him of corrupting memory.

    (Epilogue: It turns out that the graphics folks were right. It was that other component that was corrupting the memory.)

  • The Old New Thing

    I took the Monorail to the Shadow of the Moon


    It turns out that the replacement movie wasn't any of the ones I listed. Instead, I decided to see In the Shadow of the Moon, a mid-week performance in Seattle. Since it was also a fantastically warm sunny day, traffic into Seattle was a nightmare. As the bus crawled along the highway, I had to do some mental calculations. I'm definitely going to miss my connecting bus downtown (the number 4 at 6:05pm); what's the best recovery plan? It turns out that my decision, in retrospect, was the correct one, but it was merely a lucky guess.

    I arrived downtown at 6:17pm, intending to transfer to the 3 or 4 bus to Seattle Center, home of the SIFF Cinema theater. I was just too late for the 6:15pm bus, and right at the start of the transition from peak service to off-peak service. The next bus was at 6:35pm, which would put me at Seattle Center at around 6:45. Add in time for walking from the bus stop to the theater and waiting in line to pick up my tickets, and that puts me dangerously close to missing the 7pm show.

    I briefly considered getting off at REI and taking the 8, but I didn't know how often it ran, and if I missed, I would be out in the middle of nowhere. (Turns out the 8 runs every half hour, and the next bus was the 6:35, which would have gotten me to Seattle Center at 6:45, no better than the safer plan of taking the 3 or 4.)

    Aha, the Monorail runs every ten minutes. It's 6:17. Even in the worst case, I'm still way ahead. (They don't publish a timetable. You just buy your ticket and take your chances.)

    Turns out it was the worst case. I arrived at the ticket booth just as the doors closed. But the next one arrived at 6:27, as promised, and just a few minutes later, I was at the Space Needle. A brisk walk to the SIFF Cinema theater and I had plenty of time to pick up my ticket and get in line.

    I've lived in the Seattle area for over fifteen years, and this was my first Monorail ride.

    Recapping one week of SIFF:

    2 stars out of 5 12:08 East of Bucharest: The real movie was the call-in program that addresses the question of whether there was or wasn't a revolution in the town. The first half of the movie was vignettes of a small town in Romania. They were sometimes interesting, sometimes tedious (do we really have to follow a car for two minutes as it drives through the streets of town?), and they felt like filler and "backstory" for the main story. If you showed up 45 minutes late and just caught the call-in program, you'd still get 90% of the enjoyment of the movie. One brief plot line from the first half of the movie comes back in the second; aside from that, you really didn't miss much. I give it a 2 out of 5 based on the strength of the second half.

    4 stars out of 5 Fair Play: SIFF labelled this a black comedy, and there were indeed a few black-comedic moments at the beginning, but it really would be better-described as a tense thriller. The build-up was well-done, and the twist at the end makes you mentally rewind the movie and replay it in your head so you can view the motivations of one of the characters in a different light. I give it a 4 out of 5, gaining points from the wonderful squash game, but losing points because the canyoneering trip was a bit too convenient from a storytelling point of view.

    5 stars out of 5 In the Shadow of the Moon: This was absolutely wonderful, a documentary consisting of stunning never-before-seen NASA footage from the Apollo missions and interviews with most of the surviving astronauts who have been to the moon. (Of the astronauts, all of whom are extremely well-spoken and quite funny, Michael Collins steals the show.) If this movie goes into general release, I strongly encourage every space buff to run, don't walk, to see it. The footage of the Saturn V launch brought tears to me eyes. I give it a 5 out of 5.

    There's a spectacular shot taken from the inside of a spent stage: You watch the next stage ignite and the spacecraft fade off into the distance, then as the spent stage loses attitude, the earth comes into view before the film finally runs out. During the Q&A after the movie, one person asked the director, "How did the film of that sequence survive re-entry?" The answer: The film was ejected from the spent stage and fell to earth. High-altitude planes were in pursuit with giant nets trailing out behind them. That was one insane game of "catch".

    The special surprise guest at the screening was Bill Anders, the crewmember from Apollo 8 who took the famous Earthrise photo. He quipped that Frank Borman actually took the first Earthrise photo, but Borman had the disadvantage of using the camera loaded with black-and-white film; Anders had color film in his camera.

    Bonus story #1 from Gene Cernan: "My father was alive when the Wright brothers made their first flight; he could hardly believe that I walked on the moon. My son was five years old; he thought it was no big deal."

    Bonus story #2 from Charles Duke: "After I returned, the flight doctor told me that at launch my heart rate was 144." A beat. "John's was 70." Cut to interview with John Young: "I'm old. My heart can't go any faster."


    5 stars out of 5 Would pay money to see again by myself.
    4 stars out of 5 Would see again if it were free or if seeing it with others.
    3 stars out of 5 Would recommend to others.
    2 stars out of 5 Okay, but wouldn't recommend to someone not already interested.
    1 star out of 5 Would advise against.
    0 stars out of 5 Waste of my time.

    Note: The rating scheme has been revised since this article was originally posted.

Page 4 of 5 (41 items) 12345