Your browser does not support JavaScript! Skip to main content
Free 30-day trial Customer portal Contact
 
Rapita Systems
 

Industry leading verification tools & services

Rapita Verification Suite (RVS)

  RapiTest - Unit/system testing   RapiCover - Structural coverage analysis   RapiTime - Timing analysis (inc. WCET)   RapiTask - Scheduling visualization   RapiCoverZero - Zero footprint coverage analysis   RapiTimeZero - Zero footprint timing analysis   RapiTaskZero - Zero footprint scheduling analysis

Multicore verification

  CAST-32A Compliance   Multicore Timing Solution   RapiDaemons

Services

  V & V Services   Qualification   Training   Tool Integration  Support

Industries

  Aerospace (DO-178C)   Automotive (ISO 26262)   Space

Other

  RTBx   Mx-Suite   Software licensing   Product life cycle policy

Latest from Rapita HQ

Latest news

FACE Virtual Technical Interchange Meeting
RVS 3.14 Launched
Propelling the next generation of scientists
Another successful DO-178C Virtual Training Course complete
View News

Latest from the Rapita blog

Metrowerks CodeTest - How and why to upgrade
Leveraging FACE Conformance Artifacts to Support Airworthiness
Assured Multicore Partitioning for FACE Systems
Going above and beyond the quality standards
View Blog

Latest discovery pages

matlab_simulink MATLAB Simulink MCDC coverage and WCET analysis
code_coverage_ada Code coverage for Ada, C and C++
amc-20-193 AMC 20-193
embedded_software_testing Embedded Software Testing Tools
View Discovery pages

Upcoming events

DO-178C Virtual Workshop
2021-03-08
FACE Virtual Technical Interchange Meeting
2021-03-23
Safe Use of Multi-Core Processors Seminar
2021-04-05
View Events

Technical resources for industry professionals

Latest White Papers

Multicore Timing Analysis for DO-178C
Seven Roadblocks to 100% Structural Coverage (and how to avoid them)
Eight top code coverage questions in embedded avionics systems
View White Papers

Latest Videos

Streamlined software verification thumbnail
Streamlined software verification with RVS 3.14
Qualification guidance thumbnail
Clear qualification guidance with RVS qualification kits
Optimizing tests to run after code changes with RVS
Easily manage test runs with RapiTest
Test Templates thumbnail
Generating test templates with RapiTest
View Videos

Latest Webinars

Incremental Assurance of Multicore Integrated Modular Avionics (IMA)
Certifying multicore systems for DO-178C (CAST-32A) projects
Airborne Safety with FACE™ in the Digital Battlespace
View Webinars

Latest Case studies

Cobham Aerospace Connectivity: RapiCover continues to deliver on the most challenging targets
DO-178B Level A Embraer FCS
Validation of COTS Ada Compiler for Safety-Critical Applications
View Case studies

Discover Rapita

Who we are

The company menu

  • About us
  • Customers
  • Distributors
  • Locations
  • Partners
  • Research projects
  • Contact us

Careers

Careers menu

  • Current opportunities & application process
  • Working at Rapita

US office

+1 248-957-9801
info@rapitasystems.com
41131 Vincenti Ct.
Novi, MI, 48375
USA

UK office

+44 (0)1904 413945
info@rapitasystems.com
Atlas House
York, YO10 3JB
UK

Back to Top

Function pointers and their impact on stack analysis

Breadcrumb

  1. Home
  2. Blog
  3. Function pointers and their impact on stack analysis
2015-03-04

Introduction

Function pointers present a real problem for static code analysis, including when calculating stack usage. Understanding software stack requirements is an activity that is required for several standards/guidelines including DO-178B and DO-178C. Nevertheless, function pointers are supported and therefore prevalent in most system-level languages (C and Ada both have them, whilst they are used all the time with C++). Any operating system, higher-level function, or middleware providing hooks will usually resort to function pointers for the user-side part of their operation.

Establishing which functions can be called indirectly can be time-consuming and error-prone, especially when done by hand. It is even sometimes impossible to establish manually which functions may be called indirectly - for example when some part of a finished executable has no source available.

In some situations failure to analyze function pointers can even lead to overly optimistic results - for example when stack analysis does not know where to look for sub-calls and therefore assumes an indirect call uses zero stack. Really, the only way to reliably trap function calls is by observation - i.e. dynamic analysis. stack usage table

Source and object instrumentation

Function pointer calls can be done through source code analysis when source is available. To be completely thorough though, object code analysis is required. This means looking at the assembly or machine-code level analysis of the compiled source, and has the added benefit of being able to catch all indirect function calls, even if they are made from part of an executable for which no source code exists. It is full of complications though - in order to be meaningful in a report a map must exist between the assembly code that has been analyzed, and the source code it originates from. Luckily debuggers have been doing a good job of providing this kind of mapping for many years and algorithms exist for providing linear-time mappings from assembly to source with relatively low memory overhead.

Recording the results

Each time an instrumented function pointer is seen, a map must be recorded between the origin of the call and the destination function. Some chips and hardware have capabilities for on-chip tracing which helps us to be able to produce a trace of, say, all branch statements made by the processor. Sadly this is not commonplace, and other strategies must be employed in order to extract the required information.

Naively this can be done via a trace - every time a function pointer call is seen the original location of the call and the function being called can be output to a trace. We do this via instrumentation of the code to call tracing functions which store the relevant data. The problem with this, is that the trace is unbounded - observe the same indirect call 2000 times and you will have 2000 records of this in your trace. However, there are only a finite number of combinations of functions and pointers that can be made, bounded by (number of functions * indirect call locations). Therefore, it is straightforward enough to provide a map of caller to callee which updates in linear-time. In fact, if speed and memory are not an issue during your analysis run then a map can be used as good alternative to tracing.

It is also possible to provide constant-time instrumentation as a bitmap (one bit per caller-callee pair) via object-code level instrumentation, where access to the assembly allows more controlled injection of data and instrumentation code.

Identifying indirect calls

One of the major issues with object code analysis is the number of creative (and, thanks to optimization, often employed) ways that a function can be called indirectly. Partly this is down to the processor, and partly down to the compiler.

On the ARM processor, for example, the program counter is just a register that can be written to like any other - any instruction that can alter a register (which is pretty much all of them) can alter the program counter and therefore has the potential to be used for indirect calls. These instructions can be used interchangeably with the return from a subroutine. Ironically the instructions used for direct function calls on the ARM are among the few which are not capable of invoking indirect calls. In addition the instruction to preserve and update the return-from-subroutine register may appear in a variety of forms and is not bound to the updating of the program counter.

An example of a hand-coded indirect function call on the ARM processor:

.indirect_function
STMIA R13!, {R1-R3, R14}  -- Preserve calls
ADR   R14, subcall_return -- Move the address of the return into the link R14
MOV   R0, #15             -- Move the constant 15 into R0
MOV   PC, R1              -- Move the contents of R1 into the program counter
.subcall_return
LDMIA R13!, {R1-R3, PC}   -- Return from this routine, restoring R0-R3 at the same time

Luckily there are some processors, such as the PowerPC, where identification of indirect calls falls to a single dedicated instruction, which is therefore easily identified. Identifying the patterns which a specific compiler uses for indirect function calls (as opposed to other jumps in general - indirect or otherwise) is a task that needs to be performed on a per-compiler basis. Where various binaries from different compilers are packaged together (or even, as is likely with operating systems, hand-coded assembly is provided) this task becomes even more complex, though not impossible.

Conclusion

In conclusion, function pointer analysis is an area fraught with complexity - the more it is looked at, the more corner-cases we find. In order to perform to the most optimal level with the greatest completeness object-code analysis is required; however this comes with its own issues, some of which are considerably harder to deal with than others. You can find out more about tools for worst case stack analysis in the technical note below.

White papers

  • Solutions
    • Rapita Verification Suite
    • RapiTest
    • RapiCover
    • RapiTime
    • RapiTask

    • CAST-32A Compliance Package
    • Verification and Validation Services
    • Qualification
    • Training
    • Integration
  • Latest
  • Latest menu

    • News
    • Blog
    • Events
    • Videos
  • Downloads
  • Downloads menu

    • Brochures
    • Webinars
    • White Papers
    • Case Studies
    • Product briefs
    • Technical notes
    • Software licensing
  • Company
  • Company menu

    • About Rapita
    • Customers
    • Distributors
    • Industries
    • Locations
    • Partners
    • Research projects
    • Contact
  • Discover
    • AMC 20-193
    • What is CAST-32A?
    • Multicore Timing Analysis
    • MC/DC Coverage
    • Code coverage for Ada, C & C++
    • Embedded Software Testing Tools
    • Aerospace Software Testing
    • Automotive Software Testing
    • Certifying eVTOL
    • DO-178C Testing
    • WCET Tools
    • Worst Case Execution Time
    • Timing analysis (WCET) & Code coverage for Matlab Simulink

All materials © Rapita Systems Ltd. 2021 - All rights reserved | Privacy information Subscribe to our newsletter