Static analysis and low-level C programs that access the representation of addresses

Written by Pascal Cuoq

Introduction

It is sometimes easier to see how things can work out in hindsight than when you are in the moment.

 I had only recently arrived at my previous position, as a research engineer when, at a large internal event, I heard the head of the division I was in explain the innovation pipeline in terms of the 4Ps: Papers, Patents, Prototypes, and finally Products. The division I was in was dedicated to applied research. Our job there, as his speech explained, was essentially to produce patents and prototypes. It was implied that papers (aka research articles) shouldn’t be the main focus of our activities. And while the natural next step for a prototype we build might be turning it into a product, this transformation would happen elsewhere too.

 I would have a lot to say about the relevance of patents in my field, but that, my friends, would be for another blog post. I did, however, continue to work there on a research prototype for eight years, and in recent years, as Chief Scientist of the company I co-founded, on an innovative product based on the prototype in question, exactly as the 4Ps innovation pipeline lays out. In retrospect, I think it was a useful high-level explanation.

 Being concerned with practical ideas, and actually bringing them to fruition, engineering constraints often come into play: one industrial partner or customer has a specific problem, and you have the glimmer of an idea for an elegant approach, that you are quite certain you could convert into a full-blown solution. But by the time you reflect on this solution and how to implement it, the project in which the problem arose would be finished, and since the problem is specific to that partner and to that project, the solution may be obsolete. Will the same question ever arise again? Would the full implementation of the solution inside the prototype or product you are working on, if you went that far, become a form of technical debt, making it more difficult to tackle other, more interesting problems? It is always difficult to tell.

 Months pass, new customers, industrial partners, and projects arrive and prevent you from digging any further. Many unaddressed needs, and ideas for tackling them, remain unimplemented. After several years, you may have collected many such loose threads you never had the time to do something with. But, sometimes, some of these loose threads may knit together into a single consistent solution. These moments are rarer than one might think if they have not been in this situation: it is easy to underestimate the likelihood that a solution to one of the questions, implemented immediately, will hinder rather than help when the next one arises.

This post is about a collection of seemingly disparate problems identified during the life of TrustInSoft Analyzer, to which a common solution emerged recently. The examples come from different codebases, provided by different research partners and customers during the life of TrustInSoft Analyzer as a research prototype and as a product. The examples differ and are typical of varied software components, but they have in common that they access the representation of addresses, something that the C language allows while most other programming languages do not.

 It should be noted that while C gives access to the representation of addresses of data, the C standard regularly adds constraints limiting what C programs can do with this power. And compilers regularly re-interpret existing constraints from the standard in a more constraining way. For an analysis tool such as TrustInSoft Analyzer, or one of the research prototypes such as the one TrustInSoft Analyzer started from, it is temptingly easy to reject all or a large proportion of C programs that access representations of addresses, so that all the programs that use these representations of addresses in an invalid or dangerous way are rejected. The challenge here is to avoid throwing the baby out with the bathwater, or, since there are many C programs with different contexts and histories, to throw as few babies as possible out with the bathwater. In less gory terms, we aim at accepting as many valid C programs as possible, despite some of these programs making use of the representation of addresses, in various ways, during their computations.

Issues when analysing low-level C programs

Testing the position of addresses in memory space

Embedded software that may access different peripherals or kinds of memory through the same address space may contain idioms such as:

if ((uintptr_t) p >= (uintptr_t) FLASH_START) &&
  (uintptr_t) p < (uintptr_t) FLASH_END))

…

The example above compares the integer representations of addresses. The conversion of pointers to integers is implementation-defined but generally speaking, this idiom is safer than trying to express the same thing using a pointer comparison. The alternate version below, in which the addresses of flash_start and flash_end are set via means of a linker script, are particularly bad from the point of view of future-optimizing-C-compilers-proof code, because in principle pointer comparison with < > <= or >=  is only intended for pointers to (or one-past-the-end of) the same array.

// The addresses of flash_start and flash_end are
// set in a linker script.

// The pointer p is not an offset of either.

// NEVER use this form:

if (p >= &flash_start && p <= &flash_end)

…

Pointer arithmetic is not integer arithmetic, as the incident recorded in this old LWN article reminds us (although the details are a bit different).

 But if the pointers are converted to integers (and particularly the unsigned type uintptr_t), then we are using the familiar integer comparison. So it’s a good thing if an analyzer warning reveals that the analyzed code is using the dangerous “p >= &flash_start && …” version, but at the same time, ideally, we would like the analyzer not to warn for the uintptr_t-based version that we recommend for portability to future optimizing C compilers.

 The same idiom can also be found in industrial code with function pointers instead of data pointers:

if ((uintptr_t) p >= (uintptr_t) KERNEL_START) &&
  (uintptr_t) p < (uintptr_t) KERNEL_END)) …

Testing address alignment

Another variation yet of the check on the position of an address in memory space is the alignment check, which may look as follows.

if ((uintptr_t) p % 8 == 0)
  …

One real example that I heard about years ago was an implementation of memcpy, optimized for (then common) 32-bit platforms. The function memcpy takes source and destination pointers with no particular alignment requirements, but by handling the first and last bytes specially, it is possible to copy most of the string at the maximum speed allowed by the 32-bit bus. Since the source and destination pointers are not guaranteed to be misaligned in the same way, such an optimized implementation has a total of 16 classes of behaviors depending on the remainder of the representation of each pointer argument in the division by 4. And, as the astute reader will have guessed, the reason I was told the story of that particular memcpy implementation is that one of the 16 cases, and one only, had a bug. It can be tricky to detect such bugs: there are primitives for obtaining aligned pointers. Misaligned pointers to pass such an optimized memcpy implementation for testing purposes can be built by allocating a block a bit larger than intended as taking the right offset inside it; but these ad-hoc attempts leave a few valid-but-unused bytes at the beginning and the end of the effectively usable block, meaning that the exact kind of obscure bug we are looking for, out-of-bounds reads or writes of just one or two characters just before or just after the source or the destination, would by construction be invisible to our tests.

Assertions and alternative paths

All the tests in the examples above come of one of two flavors: either they check a property of the address that is expected to be true, or they do not expect one answer more than the other but serve to handle the address in flash/function in kernel/aligned data situation using a different different execution path than the alternative. The optimized memcpy example is one in which different values of (uintptr_t) p % 4 lead to distinct but equally possible execution paths.

 The first flavor typically takes the form of an assertion. It is a shame for the analyzer, because it works on addresses symbolically and does not assign them integer values the way a C compiler does, to be unable to prove that the assertion is always true. But on the plus side, in this scenario, the paths corresponding to the wrong value of the condition is clearly not intended to be followed. The annoying thing about the second flavor is that, by not understanding low-level aspects of the representation of addresses, the analyzer ends up following two slightly different paths that appear to it equally possible. This causes a lot of trouble in terms of wasted computing resources and puzzlement of the user who has to make sense of the analyzer’s results.

Using the low bits of known-aligned pointers as bonus storage

An aligned address is one in which a number of the low-order bits are known to be zero. Since these bits are known to be zero, the original address can be recovered through masking, even if the low-order bits in question are used to store extraneous information. This trick is seen for instance in some BDD (Reduced Ordered Binary Decision Diagrams) implementations, where the “maximal sharing” property among subtrees extends to a subtree and its negation through so-called “complemented edges”. While an “optionally complemented edge” could be represented in any programming language with a pointer and a boolean, in C, the boolean can be stored as the lowest bit of the pointer representation for space efficiency, and cleared each time the pointer needs to be accessed. This will typically look like:

// the representation of a pointer to struct node
// with the lowest-order bit used for complementing:
typedef uintptr_t compl_node;

struct node {
  vid variable;
  compl_node left;
  compl_node right;
  };

#define TRUE ((compl_node)1)
#define FALSE ((compl_node)0)
_Bool eval(compl_node cn, Bool complement, valuation v) {
  Bool complemented = (cn & (uintptr_t)1) ^ complement;
  struct node  n = (struct node )(cn & ~(uintptr_t)1);
  if (!n) return complemented;
  compl_node next = v[n->variable] ? n->right : n->left;
  return eval(next, complemented, v);
}

Conclusion

This post shows the kind of program constructs that for a long time were causing trouble to TrustInSoft Analyzer (and to be honest, to many other tools that attempt to solve similar problems, in both academia and industry). In a future post, I will tell about the solution my colleagues and I designed and implemented in order to do better on programs that use these constructs.