Tracing requirements through to object-code verification - Embedded.com

Tracing requirements through to object-code verification

Verifying object code can mean the difference between success and failure, quality and crap. But skipping the step because a standard doesn't require it or because it theoretically eats into profits is a surprisingly common practice. The author postulates that this practice is not only shortsighted but no longer valid.

Click here for more content from ESD March 2012.

No longer is it enough to write robust software. The recent trend in standards development is to prove that a project's requirements are fulfilled, even if those requirements have changed during the course of a project's lifecycle. Requirements traceability yields a more predictable outcome at deployment and responds to an increased demand for sound monitoring and management techniques during development, particularly between project phases.

Most requirements traceability stops short of object code, suggesting an implied reliance on the faithful adherence of compiled object code to the intentions expressed by the author of the source code. This can have critical consequences, such as putting people's lives risk or having a significant impact on business.

Where an industry standard is enforced, a development team will usually adhere only to the parts of standard that are relevant to their application. Object-code verification, on the other hand, ensures that critical parts of an application are not compromised by the object code, which in principle is a desirable outcome for any software–whatever its purpose. However, can object-code verification be justified as part of a test regime outside the confines of its enforcement through the required adherence to a standard–particularly in those industries where software failure brings dire consequences, and yet standards are less mature.

In this article, I explain why it's important to verify object code and how it's possible to manage requirements so you can trace them right through to object-code verification (OCV).

Standards and certifications
Irrespective of the industry and the maturity of its safety standards, the case for software that has been proven and certified to be reliable through standards compliance and a requirements-traceable process is becoming ever more compelling.

According to research directed by the U.S. National Institute of Security Technology, 64% of software vulnerabilities stem from programming errors. For example, an analysis of 3,140 medical device recalls conducted between 1992 and 1998 by the U.S. Food and Drug Administration (FDA) revealed that 242 of the recalls (7.7%) were attributable to software failures. In April 2010, the FDA warned users about faulty components in defibrillators manufactured by Cardiac Science Corp. Unable to remedy the problems with software patches, Cardiac Science was forced to replace 24,000 defibrillators. As a result, Cardiac Science's shares were hit; the company reported a net loss of $18.5 million.


Click on image to enlarge.

The medical-equipment standard IEC 62304 is designed specifically to provide suitable processes to minimize the likelihood of such problems in medical devices. Other industries have similar standards as shown in Table 1 .

Although each is tuned to a specific industry sector, these standards have much in common. In particular, the IEC 61508 industrial standard is sometimes used as a basis for other standards, including all of the others shown except DO-178B/C.

One example of how this commonality of purpose shows itself is in the use of Safety Integrity Levels. In each case, a risk assessment is completed for every software project to assign the required assessment safety level of each part of the system. The more demanding the safety level, the more rigorous and thorough the process and testing need to be.
Requirements management and traceability
Requirements traceability is widely accepted as a development best practice to ensure that all requirements are implemented and that all development artifacts can be traced back to one or more requirements. The automotive industry's draft standard ISO 26262 requires bidirectional traceability and has a constant emphasis on the need for the derivation of one development tier from the one above it (see sidebar).

Maintain bidirectional traceability of requirements
The intent of this specific practice is to maintain the bidirectional traceability of requirements for each level of product decomposition. When the requirements are managed well, traceability can be established from the source requirement to its lower level requirements and from the lower level requirements back to their source. Such bidirectional traceability helps determine that all source requirements have been completely addressed and that all lower level requirements can be traced to a valid source. Requirements traceability can also cover the relationships to other entities such as intermediate and final work products, changes in design documentation, and test plans.

–Source: ISO 26262

While this is a laudable principle, last minute changes of requirements or code made to correct problems identified during test tend to put such ideals in disarray. Many projects fall into a pattern of disjointed software development in which requirements, design, implementation, and testing artifacts are produced from isolated development phases. Such isolation results in tenuous links between requirements, the development stages, and/or the development teams.

The traditional view of software development shows each phase flowing into the next, perhaps with feedback to earlier phases, and a surrounding framework of configuration management and process (e.g., Agile, RUP). Traceability is assumed to be part of the relationships between phases. However, the reality is that while each individual phase may be conducted efficiently, the links between development tiers become increasingly poorly maintained over the duration of projects.


Figure 1: RTM sits at the heart of the project, defining and describing the interaction between the design, code, test and verification stages of development.
Click on image to enlarge.

The answer to this conundrum lies in requirements traceability matrix (RTM) as shown in Figure 1 , which sits at the heart of any project even if it's not identified as such. Whether the links are physically recorded and managed or not, they still exist. For example, a developer creates a link simply by reading a design specification and uses that to drive the implementation.


Figure 2: The requirements traceability matrix (RTM) plays a central role in a development lifecycle model. Artifacts at all stages of development are linked directly to the requirements matrix. Changes within each phase automatically update the RTM so that overall development progress is evident from design, coding, and test through to object-code verification at the 6th tier.
Click on image to enlarge.

This alternative view of the development landscape illustrates the importance that should be attached to the RTM. Due to this fundamental centrality, it's vital that project managers place sufficient priority on investing in tooling for RTM construction. The RTM must also be represented explicitly in any lifecycle model to emphasise its importance, as Figure 2 illustrates. With this elevated focus, the RTM is constructed and maintained efficiently and accurately.

When the RTM becomes the center of the development process, it has an impact on all stages of design from high-level requirements through to target-based deployment and OCV.

The Tier 1 high-level requirements might consist of a definitive statement of the system to be developed. This tier may be subdivided depending on the scale and complexity of the system.

Tier 2 describes the design of the system level defined by Tier 1. Above all, this level must establish links or traceability with Level 1 and begin the process of constructing the RTM. It involves the capture of low-level requirements specific to the design and implementation and that have no impact on the functional criteria of the system.

Tier 3's implementation refers to the source/assembly code developed in accordance with Tier 2. Verification activities include code rule checking and quality analysis. Maintenance of the RTM presents many challenges at this level, as tracing requirements to source-code files may not be specific enough and developers may need to link to individual functions. In many cases, the system is likely to involve several functions. Traceability of those functions back to Tier 2 requirements includes many-to-few relationships. It's very easy to overlook one or more of these relationships in a manually-managed matrix.

In Tier 4 host-based verification, formal verification begins. Using a test strategy that may be top-down, bottom up, or a combination of both, software simulation techniques help create automated test harnesses and test-case generators as necessary. Test cases should be repeatable at Tier 5 if required.

At this stage, we confirm that the software is functioning as intended within its development environment, even though there is no guarantee it will work when in its target environment. However, testing in the host environment first allows the time-consuming target test to confirm that the tests remain sound in the target environment.

Tier 5's target-based verification represents the on-target testing element of formal verification. This frequently consists of a simple confirmation that the host-based verification performed previously can be duplicated in the target environment, although some tests may only be applicable in that environment itself.

Tier 6 takes the target-based work a stage further, to tie in the comparison of the object and source code as part of the RTM and an extension to it.

Object-code verification
The aerospace DO-178B standard (6.4.4.2 Structural Coverage Analysis) defines OCV as:

“The structural coverage analysis may be performed on the source code, unless the software is Level A and the compiler generates object code that is not directly traceable to source code statements. Then, additional verification should be performed on the object code to establish the correctness of such generated code sequences. A compiler-generated array bound check in the object code is an example of object code that is not directly traceable to the source code.”

Object-code verification hinges on how much the control flow structure of the compiler-generated object code differs from that of the application source code from which it was derived.

Object-code control flow versus source-code control flow: Consider the very simple source code in Listing 1 .

Listing 1:

void f_while4( int f_while4_input1, int f_while4_input2 ){   int f_while4_local1, f_while4_local2 ;   f_while4_local1 = f_while4_input1 ;   f_while4_local2 = f_while4_input2 ;   while( f_while4_local1 < 1 ||  f_while4_local2 > 1 )     {        f_while4_local1 ++ ;        f_while4_local2 — ;     }}

This C code can be demonstrated to achieve 100% source-code coverage by means of a single call:

f_while4(0,3);

and can be reformatted to a single operation per line (shown in Listing 2 ).

Listing 2:

1  void1    f_while4 (1    int f_while4_input1 ,1    int f_while4_input2 )1    {1      int1        f_while4_local1 ,1        f_while4_local2 ;1	f_while4_local1 = f_while4_input1 ;1	f_while4_local2 = f_while4_input2 ;————————————————————————————————————-2      while2        (2        f_while4_local1 < 12        ||————————————————————————————————————-3        f_while4_local2 > 1————————————————————————————————————-4        )————————————————————————————————————-5        {5          f_while4_local1 ++ ;5          f_while4_local2 — ;5        }————————————————————————————————————-6    }

Figure 5: A dynamic flowgraph showing 100% assembler code exercised through additional function calls.
Click on image to enlarge.

Figure 4: A dynamic flow graph showing the assembler code exercised through a single function call.
Click on image to enlarge.

Figure 3: A dynamic flowgraph showing the source code exercised through a single function call.
Click on image to enlarge.

The prefix for each of these reformatted lines of code identifies a “basic block”–that is, a sequence of straight line code. The resulting flow chart for the function shows both the structure of the source code and the coverage attained by such a test case with the basic blocks identified on the flow chart nodes (Figure 3 ).

The object code generated by a compiler will depend on the optimization setting, the compiler vendor, the target, and a host of other issues. Listing 3 shows just one example of resulting (reformatted) assembler code generated by a widely-used, commercially available compiler with optimization disabled.

Listing 3:

    39 _f_while4:    40               push      fp    41               ldiu      sp,fp    42               addi      2,sp    43               ldi       *-fp(2),r0    ; |40|    44               ldiu      *-fp(3),r1    ; |41|    45               sti       r0,*+fp(1)    ; |40|    46               sti       r1,*+fp(2)    ; |41|    47               ble       L3            ; |43|    New test 2    48 ;*     Branch Occurs to L3            ; |43|    49               ldiu      r1,r0    50               cmpi      1,r0          ; |43|    51               ble       L5            ; |43|    52 ;*     Branch Occurs to L5            ; |43|    New test 3    53i    54 L3:    55               ldiu      1,r0          ; |45|    56               ldiu      1,r1          ; |46|    57               addi      *+fp(1),r0    ; |45|    58               subri     *+fp(2),r1    ; |46|    59               sti       r0,*+fp(1)    ; |45|    60               cmpi      0,r0          ; |43|    61               sti       r1,*+fp(2)    ; |46|    62               ble       L3            ; |43|    New test 1    63 ;*     Branch Occurs to L3            ; |43|    64               ldiu      r1,r0    65               cmpi      1,r0          ; |43|    66               bgt       L3            ; |43|    67 ;*     Branch Occurs to L3            ; |43|    68    69 L5:    70               ldiu      *-fp(1),r1    71               bud       r1

The flow chart looks quite different for the assembler code–and using the identical test case generates a quite different flow graph both in terms of appearance and in terms of coverage (Figure 4 ).

It's clear from the flow chart and the assembler code that more tests are necessary to achieve 100% code coverage.

  • New test 1. Line 62. End of block 3. Branch to L3. This ble branch always evaluates to false with the existing test data because it only exercises the loop once, and so only one of the two possible outcomes results from the test. Adding a new test case to ensure a second pass around that loop exercises both true and false cases. A suitable example can be provided thus:

    f_while4(-1,3);

  • New test 2. Line 47. End of block 1. Branch to L3. This code contains an “or” statement in the while loop conditions. Both the existing test cases result in the code:

    f_while4_local1 < 1

    returning a "true" value. The addition of a new test case to return a "false" value will address that:

    f_while4(3,3);

  • New test 3. Line 52. End of block 2. Branch to L5. The remaining unexercised branch is the result of the fact that if neither of the initial conditions in the "while" statement is satisfied then the code within the loop is bypassed altogether via the ble branch.

    So, the final test is added will provide such a circumstance:

    f_while4(3,0);

    This results in 100% statement and branch coverage of the assembler code, as shown in Figure 5 .

  • So--to achieve 100% coverage of the asembler code, four tests are required:
      f_while4(0,3);   f_while4(-1,3);  f_while4(3,3);  f_while4(3,0);

Why verify object code
For most development teams software testing traditionally has consisted of only functional system testing. The problem was that often the test data selected exercised only a limited amount of the source code while in-the-field data was quite different in nature. As a result, much of the code was only exercised for the first time when it was actually deployed.


Figure 6: Code exercised both on site and by functional testing is likely to include many unproven execution paths.
Click on image to enlarge.

Even in the field, it's highly likely that circumstances required to exercise much of the code have never occurred, and so even legacy applications have sustained little more than an extension of functional system testing through their in-field use (see Figure 6 ).

Consider that problem in terms of the data sets used to exercise that code. It is a natural outcome that most circumstances will generate data that exercises a particular part of the code that becomes well proven--but it's the exceptional cases that occur rarely that cause failure. Indeed, anyone who has been involved with the correction of problems seen in the field will confirm how frustrating the reproduction of relevant circumstances can be.


Figure 7: Ensuring all code is exercised using structural coverage.
Click on image to enlarge.

Structural coverage (see Figure 7 ) addresses this problem by providing evidence that all of the code base has been exercised. Such an approach has been proven to reduce the risk of failure and consequently is specified in most, if not all, industrial standards concerned with safety.

Object-code coverage
Structural code coverage offers a proven mechanism for ensuring that software is robust and safe. But we've already established that merely exercising all of the source code does not prove that all of the object code has been similarly exercised and proven. True, it's less likely that an unexercised route through the object code will lead to system failure. But even lesser risks can be unacceptable if a system is sufficiently safety-, commercially-, or mission-critical.

In short, how big are your risks?

Consider the fact that our example mismatch between source- and object-code flow charts was generated in a compiler with optimization disabled. Many more differences are likely as the result of compiler interpretation and optimization. While traditional structural coverage techniques are applied at the source-code level, the object code executes on the processor--and that's what really matters.

Any differences in control flow structure between the two can make for significant and unacceptable gaps in the testing process. In some industries, these gaps are acknowledged and accounted for. For example, in aerospace, the DO-178B standard requires developers to implement OCV facilities for those elements of the application that have a Level-A (safety-critical) classification. While this is often a subset of the application as a whole, it has traditionally represented a significant amount of testing effort and hence has always required considerable resources.

Opportunities to implement automated, compiler-independent processes can help to reduce overall development costs by considerable margins, and conversely make OCV commercially justifiable in other fields.


Figure 8: The automation of object-code verification can reduce the necessary amount of testing effort by a considerable margin.
Click on image to enlarge.

Automated OCV
Automated OCV solutions can provide a complete structural coverage analysis solution for both source and object code from unit to system and integration levels. Typical solutions combine both high- and object-level (assembler) code analysis tools, with the object-level tool variant being determined by the target processor that the application is required to run on. A typical example might see C/C++ and TMS320C25x Assembler analysis tools teamed together to provide the required coverage metrics, as shown in Figure 8 .

OCV at the unit level
Some automated tools enable users to create test cases for structural coverage of high-level source and apply the same test cases to the structural coverage of the corresponding object code. A driver program is generated by such a unit-test tool that encapsulates the entire test environment, defining, running, and monitoring the test cases through initial test verification and then subsequent regression analysis. When used for OCV, this driver may linked with either the high-level source unit or the associated object code. In so doing, users can apply a uniform test process and compare code in order to determine any discrepancies or deficiencies, as Figure 9 demonstrates.


Figure 9: Object code and source flow graphs illustrate the structure and coverage of the high- and low-level code, and hence any discrepancies between them.
Click on image to enlarge.

If structural coverage discrepancies or deficiencies are identified at the object level, users are presented an opportunity to define additional test cases to close any gaps in the test process. The obvious advantage of identifying and applying corrective action at such an early development stage is that it's much easier and cheaper. It also significantly increases the quality of the code and the overall test process with the latter reaping benefits at the later stages of integration and system testing and onward in the form of reduced failure rates and maintenance costs when the application is in the field.

While the code is still under development, developers can also benefit from the considerable additional test feedback together with satisfying the necessary OCV requirements in a highly automated and cost-effective manner. The results of these analysis facilities can be fed back to the development team with the possibility that further code and design deficiencies may be identified and rectified, further enhancing the quality of the application as a whole.

Making object-code verification the norm
It's clear that OCV has always involved significant overhead and even in the aerospace sector, it's only enforced as a requirement for the most demanding safety integrity levels. Even then, the elements nominated for OCV in these applications are usually a subset of the application as a whole--a specialist niche indeed.

Until quite recently, unit test has been considered a text-book nicety and yet the ever-increasing capabilities and ease of use of automated unit-test tools has introduced a commercial justification of such techniques even when risks are lower.

Most applications include key elements in the software; a subset of code that's particularly critical to the success of the application and can be identified in the application requirements. The software requiring OCV can be identified and traced through an extension to the RTM.

The advent of tools to automate the whole of that process from requirements traceability right through to OCV challenges the notion that the overhead involved can only justify the technique in rare circumstances. Just as for unit test before it, the time has come for OCV to be commercially justifiable in a much broader range of circumstances.

Mark Pitchford is a field applications engineer with LDRA, where he specializes in software test.

This content is provided courtesy of Embedded.com and Embedded Systems Design magazine. See more content from Embedded Systems Design and Embedded Systems Programming magazines in the magazine archive.
This material was first printed in March 2012 Embedded Systems Design magazine.
Sign up for subscriptions and newsletters.
Copyright © 2012
UBM--All rights reserved.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.