Geoff Chappell - Software Analyst
The DPA_Merge function dates from 1997 and seems not to have been documented by Microsoft until 2005 or 2006. For all its life so far, i.e., up to and including version 6.10 for Windows Vista SP1, the DPAM_INTERSECT case of the DPA_Merge function is unsafe to use due to a coding error. Microsoft seems never actually to use this case, else the bug might have been fixed long ago. Note in particular that the DPAM_UNION case, which has long seen real-world use by Microsoft, both within the shell and from Internet Explorer, started with a very similar bug which was corrected for version 5.80.
This history perhaps shows as well as any that defects in software can be spotted by independent review of binary code even in preference to a review of source code. Of course, programmers at Microsoft may face all sorts of pressure to identify just the coding error at the root of some reported problem and are perhaps not permitted the luxury of understanding the whole of the code for what it actually does. Still, it is striking that one bug in the function got fixed without realising (or attending to) its logical partner. A reader of binary code is more naturally directed to deciphering the whole logic of the whole code and may even benefit from not being exposed to comments (which may offer false assurances about the soundness of an algorithm).
A summary may help for understanding the bug. The DPA_Merge function works with two Dynamic Pointer Arrays. A comparison function defines an ordering, both within a DPA and between the two DPAs. The first DPA is a target. The second is a source. In the DPAM_INTERSECT case, the function is to modify the target so that each item in the output target corresponds to a matched pair in the input source and input target, thus making the output target a sort of intersection of the input source and input target. The bug is that items remain in the target if they are lower than all source items.
To demonstrate the bug, I have a console application work with simple arrays and with comparison and merge functions that are nearly trivial. Each pointer in each array points to nothing more sophisticated than an unsigned integer. Pointers are compared just by the numerical value of the integers that they point to. Where the merge function is presented with matching pointers, it chooses the pointer that is already in the target DPA. In effect, the DPA_Merge function is made to work with sets of numbers. For example, the commands
dpamerge /i {1,2,3,4} {2,3,5}
dpamerge /u {1,2,3,4} {2,3,5}
should calculate respectively the intersection and union of the two sets {1,2,3,4} and {2,3,5}. The expected results, as known even to primary school students, are {2,3} and {1,2,3,4,5}, but all known versions of DPA_Merge compute the intersection as {1,2,3} because the target item 1 is lower than all the source items 2, 3 and 5.
For distribution, the built program (x86) is supplied with source code, compressed into one zip file: download the DPAMERGE bug demonstration. Run from a Command Prompt (though of course I advise that you check for yourself that the program is what it says and that you rebuild it if you want). To learn of additional command-line switches for closer inspection of the function’s behaviour, run with the /? switch.