Finding potential stack overflow errors

From Insight-9.0

Jump to: navigation, search

Contents

The Klocwork Stack Overflow Analyzer for C/C++ calculates potential stack overflow errors. It uses a special metric, Maxim Acyclic Stack Size, which uses a Directed Call Graph starting from entry functions.

The Analyzer works with tables resulting from a Klocwork C/C++ integration-build analysis (from kwbuildproject). The Analyzer allows you to

  • specify entry functions or use default entry functions (nodes with no calls to them)
  • specify a stack size for each entry function
  • identify functions with maximum stack size
  • identify recursive functions with the minimum number of loops required to overflow the stack
  • print information about a selected function
  • visualize the call graph of the application, focusing on stack usage issues

The Stack Overflow Analyzer is included with both the Klocwork Server and User packages.

For usage and options, see kwstackoverflow.

Tip: Include the dot utility in your path before running the Analyzer. You can find the dot application at <Klocwork_install>/3rdparty/bin.

How do I...

Find potential stack overflow problems

Run the Analyzer with the --tasks-def <tasks.def_file> or --config <config_file> option.

The tasks.def and configuration files provide information about entry functions and stack size in different formats. An entry function is the main point of entry to a thread, task, process or application. The output is a list of all possible stack overflow problems.

Run the Analyzer with the --entry <entry_function_name> and --top 10 options.

The output is a list of the top ten functions with maximum stack consumption for the specific task.

Visualize a stack trace

To create a visual call graph of a potential stack overflow, run the Analyzer with the --dot <file.dot> option. This creates a visualization of the call graph that can be viewed in the third-party application called Graphviz.

The ability to produce call graphs is restricted to the analysis of one task. Therefore, you must specify the entry function to the task and the stack size using the options --entry <entry_function_name> and --ss <stack_size>

Query a particular non-entry function

The Analyzer can report on the stack size of a particular function rather than an entire task. To do so, use the option --func <function_name> in combination with:

--tasks-def <tasks.def_file> or --config <config_file> to print the stack size for each task, if applicable

or

--entry <entry_function_name> to print the stack size for the specified entry function.

Analyze recursive calls

Use the --toprec 10 option to print the ten recursive functions that consume the most stack space, with a combination of the --config <config_file> or --entry <entry_function_name> options.

Configure data type sizes

Calculation of the stack frames depends on stored information about the size, in bytes, of built-in types in your software system. If the size of bytes of your built-in types matches the default sizes, Klocwork correctly calculates these metrics every time you run it.

Klocwork uses the following default sizes for built-in types:

int; 4
char;1
short;2
float;4
double;8
pointer;4

If the size of bytes of your built-in types do not match these default sizes, you need to create a "size of types" file and apply the --size-of-types <file> option to your Klocwork analysis to correctly calculate these metrics. For more information on creating and using this file, see Specifying sizes for built-in types.

View the annotated call graphs

The Stack Overflow Analyzer prints an annotated call graph in dot format. You can then use the dot utility, which is installed with the Stack Overflow Analyzer, to convert the call graph to various image formats or to Postscript. A few examples are provided below; see the dot documentation for more information (www.graphviz.org).

Tip: Include the dot utility in your path before starting the Analyzer. You can find the dot application at <Klocwork_install>/3rdparty/bin.

Legend

Green boxes - entry functions
Blue boxes - parent of marked node
Red nodes - selected/marked nodes (stack violation, top N or selected function)
Black nodes - other functions (only with -all)
Orange nodes - recursion start point
Double lined nodes - recursion end point
Black lines forward function calls
Red lines - backward function calls (backward from some of entry function point of view, if more than one)
Number on red lines - recursion depth before stack overflow occurs
Numbers in nodes:
  • X(N,Y..Z)
  • X - name of function
  • N - stack size for this function
  • Y - minimum stack size
  • Z - maximum acyclic stack size

When running dot, you specify the output format and the dot file generated by the Stack Overflow Analyzer.

Postscript file: 

dot -Tps -o <file.ps> <callgraph.dot>

Postscript file viewed using the Ghostscript tool: 

dot -Tps -o <file.ps> <callgraph.dot> && ghostview ex1.ps

GIF file: 

dot –Tgif –o <file.gif> <callgraph.dot>

PNG file: 

dot –Tpng –o <file.png> <callgraph.dot>

Examples

You can find the source code and examples of output files discussed in this section at <Klocwork_install>/samples/stackoverflow.

Tip: All example commands include <license_options>, which can be either --license-host <host> [--license-port>] or --license-file <file>. See kwstackoverflow.

The examples use this sample C application (source.c):

bar(){
int z;
fact(1);
}
fact(int n) {
print(n);
if (n<=1) return 1;
return fact(n-1)*n;
}
foo(int b){
bar();
}

main(){
int a;
foo(1);
fact(5);
bzik();
ping(10);
}

ping(int n){
if (n) {
pong(n-1);
}
}
pong(int n){
if (n) {
ping(n-1);
}
}

main1(){
pong(10);
}

You can find pregenerated tables for this sample file at <Klocwork_install>/samples/stackoverflow/tables. We ran the following command to generate these tables: 

kwcc --metrics -o tables source.c

Report problems based on config.ex4

This example shows how to report stack overflow problems using a configuration file. The example uses the configuration file config.ex4, found in <Klocwork_install>\samples\stackoverflow.

The file config.ex4 has the following contents:

main;28
main1;16

where

  • main is the name of the C language entry function
  • 28 is the stack size in number of bytes

Run the following command: 

kwstackoverflow <license_options> --config config.ex4 tables

Output similar to the following is displayed:

Error: Stack overflow possible for function @__UNDEFINED__@:print 32>28 for task main
source.c:main[local 4][max 4] at line 16
source.c:foo[local 4][max 12] at line 11
source.c:bar[local 4][max 20] at line 3
source.c:fact[local 4][max 28] at line 6
@__UNDEFINED__@:print[local 0][max 32]
The output above is a single stack overflow error report. The amount of stack for the function main is specified as 28 bytes in the configuration file config.ex4. The error report contains the detailed stack trace for the overflow (starting from a particular entry point down to the call at which the overflow occurs). The trace includes the amount of local data allocated on stack by each call in the trace and the accumulated stack size. Function names are prefixed with the corresponding file names. Note: The prefix @__UNDEFINED__@ represents a function that is referred to within the analyzed source code but for which no definition was available (usually library functions).

Create a call graph

This example shows how to create a call graph.

Run: 

kwstackoverflow <license_options> --ss 20 --all --dot ex1.dot tables

The maximum stack size for this example is set to 20 bytes using the --ss option.

You’ll see this output:

Error: Stack overflow possible for function @__UNDEFINED__@:print 32>20 for task main
source.c:main[local 4][max 4] at line 16
source.c:foo[local 4][max 12] at line 11
source.c:bar[local 4][max 20] at line 3
source.c:fact[local 4][max 28] at line 6
@__UNDEFINED__@:print[local 0][max 32]
Error: Stack overflow possible for function source.c:fact 28>20 for task main
source.c:main[local 4][max 4] at line 16
source.c:foo[local 4][max 12] at line 11
source.c:bar[local 4][max 20] at line 3
source.c:fact[local 4][max 28]
Convert the .dot file to a .gif file: 
dot -Tgif -o ex1.gif ex1.dot

The graph looks like this:

Image:stk_overflow_ex2_diagram.gif

The diagram uses the following conventions:

  • Green boxes - entry functions
  • Black nodes - other functions (only when option –all is specified, otherwise the diagram will be restricted to stack issues)
  • Double lined nodes - recursion end point
  • Red nodes - selected/marked nodes (stack violation, top N or selected function)
  • Blue boxes - parent of the marked node
  • Black lines forward function calls
  • Red lines - backward function calls (backward from some of entry function point of view, if more than one)
  • Numbers in nodes:
  • X(N,Y..Z) X - name of function
  • N - stack size for this function
  • Y - minimum stack size
  • Z - maximum acyclic stack size

Create a call graph for the entry function ’main’

This example shows how to create a call graph for a particular entry function.

Run: 

kwstackoverflow <license_options> --ss 31 --entry main --dot ex2.dot tables

You’ll see this output:

Error: Stack overflow possible for function @__UNDEFINED__@:print 32>31 for task main
source.c:main[local 4][max 4] at line 16
source.c:foo[local 4][max 12] at line 11
source.c:bar[local 4][max 20] at line 3
source.c:fact[local 4][max 28] at line 6
@__UNDEFINED__@:print[local 0][max 32]
Convert the .dot file to a .gif file: 
dot -Tgif -o ex2.gif ex2.dot

This graph looks like this:

Image:stk_overflow_ex3_diagram.gif

Create a call graph for ’main’ and two recursive functions

This example shows how to create a call graph for a particular entry function, and to specify the number of recursive functions.

Run: 

kwstackoverflow <license_options> --ss 8000 --entry main --toprec 2 --dot ex3.dot tables

You’ll see this output:

Message:kwstackoverflow: For task main top recursion chain #2 ping->...->pong->ping spins=500
Message:kwstackoverflow: For task main top recursion chain #1 fact->...->fact->fact spins=997

Convert the .dot file to a .gif file: 

dot -Tgif -o ex3.gif ex3.dot

This graph looks like this:

Image:stk_overflow_ex4_diagram.gif

Check errors and print recursive functions

This example shows how to check stack overflow errors and specify the number of recursive functions.

Assume configuration file config.ex4 with the following contents (file config.ex4 in directory examples):

main;24
main1;16

Run: 

kwstackoverflow <license_options> --toprec 2 --config config.ex4 --dot ex4.dot tables

You’ll see this output:

Message:kwstackoverflow: For task main1 top recursion chain #1 pong->...->ping->pong spins=1
Error: Stack overflow possible for function @__UNDEFINED__@:print 32>28 for task main
source.c:main[local 4][max 4] at line 16
source.c:foo[local 4][max 12] at line 11
source.c:bar[local 4][max 20] at line 3
source.c:fact[local 4][max 28] at line 6
@__UNDEFINED__@:print[local 0][max 32]
Message:kwstackoverflow: For task main top recursion chain #2 fact->...->fact->fact spins=1
Message:kwstackoverflow: For task main top recursion chain #1 pong->...->ping->pong spins=1

Convert the .dot file to a .gif file: 

dot -Tgif -o ex4.gif ex4.dot

This graph looks like this:

Image:stk_overflow_ex5_diagram.gif

Image:stk_overflow_ex5_2_diagram.gif

Find the stack size for the function 'fact'

This example shows how to run the Stack Overflow Analyzer on a particular function.

Run: 

kwstackoverflow <license_options> --ss 10000 --func fact --dot ex5.dot tables

You’ll see this output:

Message:kwstackoverflow: Function fact maxStackSize=28 for task main
source.c:main[local 4][max 4] at line 16
source.c:foo[local 4][max 12] at line 11
source.c:bar[local 4][max 20] at line 3
source.c:fact[local 4][max 28]
Convert the .dot file to a .gif file:
dot -Tgif -o ex5.gif ex5.dot

The graph looks like this:

Image:stk_overflow_ex6_diagram.gif

Retrieved from "http://www.klocwork.com/products/documentation/Insight-9.0/Finding_potential_stack_overflow_errors"
Personal tools