Correlating Effectiveness of Pointer Analysis Techniques with Patterns in Embedded System Code

Embedded systems are an important part of today’s life, specific examples include—controlling devices in car, avionics in aircraft, telematic systems for traffic control, pacemakers, and control systems in nuclear reactors. In the embedded systems where safety and reliability is critical, early defect detection can prevent serious destruction. Hence, for safety critical and reactive systems the compliance checks (e.g., ISO 26262, IEC 62304, DO178B/C) have become mandatory. Ensuring this compliance using manual analysis is error prone and costly. Therefore, many compliance checks are validated using static analysis tools. Consequently, these tools have become an integral part of software development life cycle of embedded systems.

Most static analysis tools rely on a pointer analysis to get the actual memory locations pointed to by a pointer at its dereference points. If this underlying points-to information is accurate, it helps tools to gain more precision in their top level analysis [1]. This basic demand to get precise points-to information has led to the development of several pointer analysis techniques [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]. Theoretically these techniques provide different levels of precision and scalability depending on the choice of flow and context sensitivity. In particular, a flow in-sensitive analysis does not consider the ordering of statements in a program while computing the points-to information. In contrast, the ordering of statements is considered by a flow sensitive analysis. Additionally, a context sensitive analysis considers the call sequence of functions while computing the points-to information along with the ordering of statements within the functions. In general, it is assumed that precision increases when we move from flow insensitive analysis to flow sensitive analysis to context sensitive analysis, while scalability decreases in the same order.

We have developed a static analysis tool [13] to detect bugs like integer overflow-underflow, division by zero, and array index out of bound. While analyzing few embedded industry code sets, we failed to see significant improvement in the precision of the tool when using context sensitive pointer analysis in place of flow sensitive analysis. On further investigation, we found that there was no significant difference in precision of the points-to information itself. This lead to the question “Is this behavior peculiar to the code sets we were analyzing, or does it hold in most embedded code sets?”. To resolve this, we performed experiments and compared precision of the three pointer analysis techniques—flow sensitive, flow insensitive, and context sensitive —on seven diverse embedded industry code sets.

Our results show that on average in 90% cases all three analyses (mentioned in the previous paragraph) had equal precision. Moreover, these equal precision cases varied from 76% to 100% on different code sets. In particular, we found that the relative gain in precision is not only dependent on the technique but is also dependent on the code. In this paper, we detail the observed differences in precision based on code pattern and correlate the two.

Given that pointer analysis has been an active area of research for several years, similar studies exist in the literature [14, 15, 16, 17, 1, 18, 19]. However, we did not find any case study that targets embedded code sets used in industry, and reasons about the difference in precision based on patterns in embedded code. Mainly because embedded industry code sets are not openly available. We believe such case studies play a key part in designing highly targeted analysis that are more effective than general ones. The need for such targeted analysis has been reiterated and discussed [5, 14, 6, 20] several times.

The main contributions of this paper are:

• •

  Comparison of three pointer analysis techniques on seven diverse embedded industry codes, ranging in size from 3 KLOC to 59 KLOC.

• •

  Detailed analysis of correlation between embedded code patterns and pointer analysis effectiveness.

Rest of the paper is organized as follows: Section II details the pointer analysis techniques that we compared. Section III details the experimental setup. Section IV discusses results and directions for future research. Section V presents related work and Section VI concludes the paper.

In this section, we explain the model used and the pointer analysis techniques that we compared.

We performed our experiments on an intel core i-7, 8 GB RAM, windows 64 bit machine. We implemented the three pointer analysis techniques in our inhouse TCS Embedded Code Analyzer(TCS ECA) Tool [13]. In this, we included seven diverse proprietary embedded code sets from the industry. These code sets were developed by different manufacturers from the automotive industry, different teams within different organizations. Few of these code sets are safety-critical systems. Table II presents the characteristics of these code sets. In particular, the size of code sets range from 3 to 59 KLOC, while the number of functions are in the range of 30 to 790. Only one of the code set (i.e., CAN1) contains heap allocation calls, and 3 code sets have 2 to 25 function pointer dereferences. Overall pointer dereference instances range from 52 to 3047 across code sets.

We treat each level of a multi-level pointer dereference as a different Point of Interest (PoI). Subsequently, for each PoI where a pointer ptr is dereferenced, we compute points-to information ptdSet corresponding to the three pointer analyses:

• •

  Flow Insensitive Information (FIS) = ptdSet_FIS

• •

  Flow Sensitive Information (FS) = ptdSet_FS

• •

  Context Sensitive Information (CS) = { ptdSet_CSi }, where i denotes the information corresponding to the i^th context.

A context sensitive information for ptr is considered be more precise, if at least one context has more precise information compared to the corresponding FS or FIS information at the point (this includes the added precision when the client analysis can enquire points-to information in specific contexts). We compare FS, FIS, and CS informations for each ptr and bucket the judgment in one of the following pointee-relation classes:

• •

  $FIS=FS=CS$: points-to information of ptr is same in FIS, FS, and CS i.e.,

  $\forall i.\ (ptdSet_{FIS}\equiv ptdSet_{FS}\equiv ptdSet_{CSi})$

• •

  $FIS<FS<CS$: points-to information of ptr in: 1) CS is more precise than FS, and 2) FS is more precise than FIS i.e.,

  $\exists i.\ (ptdSet_{CSi}\subset ptdSet_{FS})\land(ptdSet_{FS}\subset ptdSet_{FIS})$

• •

  $FIS=FS<CS$: points-to information of ptr is same in FS and FIS, and is less precise than CS i.e.,

  $\exists i.\ (ptdSet_{CSi}\subset ptdSet_{FS})\land(ptdSet_{FIS}\equiv ptdSet_{FS})$

• •

  $FIS<FS=CS$: points-to information of ptr in CS and FS is same, and is more precise than FIS i.e.,

  $\forall i.\ (ptdSet_{FS}\equiv ptdSet_{CSi})\land(ptdSet_{FS}\subset ptdSet_{FIS})$

Observe that the above cases are mutually exclusive and exhaustive (i.e., cover all possible scenarios). More specifically, the result of FIS is an over-approximaton of result of FS which is an over-approximation of CS (since CS is flow and context sensitive). Therefore, cases where FIS is more precise than FS, or FS is more precise than CS are not possible.

Table III presents the results of our experiments, and summarizes the distribution of the PoI’s into pointee-relation classes. More specifically, in 5 out of 7 applications, more than 90% PoI had equal precision (i.e., FIS=FS=CS), for rest two application (ATCM and CAN1) there was a precision gain of 16% and 20% while moving from flow insensitive to flow sensitive analysis.

We analyzed the coding patterns, the type of pointer (constant, formal, global or local), and the type of the pointer assignments (single assignment, multiple assignment) affecting the precision. Below we describe the concrete % of occurrence of each of these patterns that led to these results.

1.$FIS=FS=CS:$ We observed that on average in 90.5% cases the flow sensitive, the flow insensitive, and the context sensitive analysis gave the same results. This result can be explained by ubiquitous presence of the following code patterns in the code we analyzed.

• •

  Constant Pointer: In this case, a pointer is declared as constant pointer and is assigned a memory address in declaration. For such case, it is intuitive that FIS=FS=CS. In the embedded code sets, information is read and written to hard coded memory addresses through constant pointers or via dereference of constant address directly. These cases contributed on average 33.7% POIs in FIS=FS=CS cases, and 31% POIs in overall cases.

• •

  Formal Pointer: A formal pointer refers to a pointer declared as a function parameter. 30.7% cases of FIS=FS=CS category are of the formal pointer dereferences. In this, we observed that the formal pointers are not reassigned in the procedure. Consequently, the points-to information for the flow insensitive and the flow sensitive analysis is same (i.e., FIS=FS) for such pointer dereferences within the function.

  Further, context sensitive analysis also does not add any value in these cases because the formal pointer is assigned the same actual parameter at all the call sites of the function. This results in the same points-to information in any context as that of FS and FIS. 4 out of 7 applications depict this behavior where formals are assigned to the same variable at all call sites. Interestingly, in many procedures formal pointers are used to manipulate the values of particular global variables/arrays through pointer mimicking the setter/getter functions in Java.

• •

  Single Assigned Pointers: pointers are assigned only once in the entire program and the assignment occurs before the dereference point, so points-to information is same in FIS, FS, and CS. We observed 16.2% cases among the FIS=FS=CS cases are of this type.

• •

  Multi Assigned Pointers: We observed that in 19.4% cases among FIS=FS=CS cases were under this category, where a pointer is assigned multiple values at different points and all definitions reach to the dereference point through at least one path which results in FIS=FS=CS.

Figure 1 presents the percentage of: Constant Pointer, Formal Pointer, Single Assignment, and Multiple Assignment in the individual applications. It also highlights that none of the pattern is prevalent across the applications, yet the overall impact on the precision is same.

2.$FIS<FS<CS:$ This category measures cases where the flow sensitivity and the context sensitivity both add some disjoint precision to the results. Even though we expected this case to be prevalent, we found only 1 out of 5403 analyzed cases of this type. In this lone case, a formal pointer was assigned different addresses at different callsites and it was conditionally updated inside an if-then branch in the procedure after which it was dereferenced in the same procedure. The calls from multiple sites with different addresses made the context sensitive analysis more precise than FIS and FS, while the re-assignment of formal pointer— which we never saw happening anywhere else in these code sets—in the if-then branch made FS more precise than FIS for dereference in the else branch. The dearth of cases in this category can be attributed to practice of not re-assigning formal pointers in the corresponding procedures.

3.$FIS=FS<CS:$ Given that we observed only 1 case of $FIS<FS<CS$ category, we can say $FIS=FS<CS$ category measures the complete impact of the context sensitivity on the precision. Here, we observed an average of 2.6% cases of this type. This indicates that context sensitivity has not added much value over a flow sensitive analysis across the code sets. One of the reason for this is that in embedded code sets, most formal pointers are used for manipulation of specific variables, meaning they will be assigned same variable at all callsites. Consequently, a context sensitive analysis over such code may not improve precision. On the other hand, we did observe improvement in 5-6% cases in applications namely ATCM, BTCM, and BCM where formal pointers were assigned different variables at different call sites, indicating context sensitive analysis’ impact is not negligible. Nevertheless, a context sensitive analysis involves significant overhead over flow sensitive analysis like maintaining contexts, separate procedure solving for each context. In such cases, it is a good idea to do a lightweight pre-analysis to anticipate the usefulness of context sensitivity before making an analysis choice.

4.$FIS<FS=CS:$ Given that CS (refers to context and flow sensitive) is at least as precise as FS i.e., $FS>CS$ is infeasible case, and $FIS<FS<CS$ has occurred only once, we can say $FIS<FS=CS$ measures the complete impact of the flow sensitivity on the precision. We found 6.8% cases of this type. Among these cases 85% cases are of the following type. An uninitialized global pointer is assigned at single location before use point. Since C semantics say uninitialized global pointer is initialized to null by default, the flow insensitive points-to information for such pointers contains null along with the actual assigned address, while the flow sensitive and the context sensitive analysis contains only the assigned address because null is killed at the assignment location. Apart from this, in 11% of the cases a local pointer was initialized with null, and it was re-assigned at single location before use, giving similar result as the above 85% cases. Lastly, in the remaining 4% of the cases pointer was assigned before and after its use point resulting into difference in the flow sensitive and the flow insensitive points to information at such use point.

Das et al. [23] showcased that the flow sensitive analysis provided almost the same level of precision on 95% cases, they showed this for large open source applications of uptill 2MLoC. Their conclusion on precision gain has been in coherence with Ruf [17], Foster [24]. Ruf et al. [17] presented an empirical study of the flow sensitive and the context sensitive analysis. They showed with caution that there can be no improvement in the precision at the dereference locations. We have shown a similar result on the embedded code sets. In our work, we also presented a reasoning based on the code patterns in the embedded code sets which was not done in the earlier work.

Engblom et al. [19] studied embedded system’s static property, they aimed to improve and guide development of worst case execution time analysis. Whereas, our focus is on pointer usage and its assignment pattern that affects the precision of pointer analysis. They also concluded that pointer analysis is necessary to obtain good results on embedded code. Liang et al. [25] and Lhotak et al. [15] evaluated the effectiveness of the context sensitive points-to analysis on the Java programs. Their results show that the context sensitivity increases the precision for some benchmarks, and the context sensitive heap abstraction is important for precision. Empirical studies by Hind et al. [16, 18] focused on comparing the flow insensitive and the flow sensitive analysis with different tuning, both studies concluded that for most applications the two type of analysis didn’t show the expected precision gain difference. They gave intuitive reasoning for such behavior, whereas we had extended it to the code level reasoning making it more concrete.

This work described an empirical study carried out to evaluate the effectiveness of three different pointer analysis techniques on seven diverse embedded code sets used in industry. We found in 90% cases the flow insensitive analysis is as precise as flow and context sensitive analysis. Subsequently, we highlighted the correlation between the precision gain and the code constructs used in the industry. We also discussed how the results of this study can be used to design targeted and effective pointer analyses for embedded industry code sets.