Movatterモバイル変換

[0]ホーム
URL:

CodeQL documentation
CodeQL resources

Analyzing data flow in C and C++

You can use data flow analysis to track the flow of potentially malicious or insecure data that can cause vulnerabilities in your codebase.

About this article

This article describes how data flow analysis is implemented in the CodeQL libraries for C/C++ and includes examples to help you write your own data flow queries.The following sections describe how to use the libraries for local data flow, global data flow, and taint tracking.

Note

The modular API for data flow described here is available from CodeQL 2.13.0. The legacy library is deprecated and will be removed in December 2024. For information about how the library has changed and how to migrate any existing queries to the modular API, seeNew dataflow API for CodeQL query writing.

About data flow

Data flow analysis computes the possible values that a variable can hold at various points in a program, determining how those values propagate through the program, and where they are used. In CodeQL, you can model both local data flow and global data flow. For a more general introduction to modeling data flow, see “About data flow analysis.”

Local data flow

Local data flow is data flow within a single function. Local data flow is usually easier, faster, and more precise than global data flow, and is sufficient for many queries.

Using local data flow

The local data flow library is in the moduleDataFlow, which defines the classNode denoting any element that data can flow through.Nodes are divided into expression nodes (ExprNode,IndirectExprNode) and parameter nodes (ParameterNode,IndirectParameterNode). The indirect nodes represent expressions or parameters after a fixed number of pointer dereferences.

It is possible to map between data flow nodes and expressions or parameters using the member predicatesasExpr,asIndirectExpr, andasParameter:

classNode{/**   * Gets the expression corresponding to this node, if any.   */ExprasExpr(){...}/**   * Gets the expression corresponding to a node that is obtained after dereferencing   * the expression `index` times, if any.   */ExprasIndirectExpr(intindex){...}/**   * Gets the parameter corresponding to this node, if any.   */ParameterasParameter(){...}/**   * Gets the parameter corresponding to a node that is obtained after dereferencing   * the parameter `index` times.   */ParameterasParameter(intindex){...}...}

The predicatelocalFlowStep(NodenodeFrom,NodenodeTo) holds if there is an immediate data flow edge from the nodenodeFrom to the nodenodeTo. The predicate can be applied recursively (using the+ and* operators), or through the predefined recursive predicatelocalFlow, which is equivalent tolocalFlowStep*.

For example, finding flow from a parametersource to an expressionsink in zero or more local steps can be achieved as follows, wherenodeFrom andnodeTo are of typeDataFlow::Node:

nodeFrom.asParameter()=sourceandnodeTo.asExpr()=sinkandDataFlow::localFlow(nodeFrom,nodeTo)

Using local taint tracking

Local taint tracking extends local data flow by including non-value-preserving flow steps. For example:

inti=tainted_user_input();some_big_struct*array=malloc(i*sizeof(some_big_struct));

In this case, the argument tomalloc is tainted.

The local taint tracking library is in the moduleTaintTracking. Like local data flow, a predicatelocalTaintStep(DataFlow::NodenodeFrom,DataFlow::NodenodeTo) holds if there is an immediate taint propagation edge from the nodenodeFrom to the nodenodeTo. The predicate can be applied recursively (using the+ and* operators), or through the predefined recursive predicatelocalTaint, which is equivalent tolocalTaintStep*.

For example, finding taint propagation from a parametersource to an expressionsink in zero or more local steps can be achieved as follows, wherenodeFrom andnodeTo are of typeDataFlow::Node:

nodeFrom.asParameter()=sourceandnodeTo.asExpr()=sinkandTaintTracking::localTaint(nodeFrom,nodeTo)

Examples

The following query finds the filename passed tofopen:

importcppfromFunctionfopen,FunctionCallfcwherefopen.hasGlobalName("fopen")andfc.getTarget()=fopenselectfc.getArgument(0)

However, this will only give the expression in the argument, not the values which could be passed to it. Instead we can use local data flow to find all expressions that flow into the argument, where we useasIndirectExpr(1). This is because we are interested in the value of the string passed tofopen, not the pointer pointing to it:

importcppimportsemmle.code.cpp.dataflow.new.DataFlowfromFunctionfopen,FunctionCallfc,Exprsrc,DataFlow::Nodesource,DataFlow::Nodesinkwherefopen.hasGlobalName("fopen")andfc.getTarget()=fopenandsource.asIndirectExpr(1)=srcandsink.asIndirectExpr(1)=fc.getArgument(0)andDataFlow::localFlow(source,sink)selectsrc

Then we can vary the source and, for example, use the parameter of a function. The following query finds where a parameter is used when opening a file:

importcppimportsemmle.code.cpp.dataflow.new.DataFlowfromFunctionfopen,FunctionCallfc,Parameterp,DataFlow::Nodesource,DataFlow::Nodesinkwherefopen.hasGlobalName("fopen")andfc.getTarget()=fopenandsource.asParameter(1)=pandsink.asIndirectExpr(1)=fc.getArgument(0)andDataFlow::localFlow(source,sink)selectp

The following example finds calls to formatting functions where the format string is not hard-coded.

importsemmle.code.cpp.dataflow.new.DataFlowimportsemmle.code.cpp.commons.PrintffromFormattingFunctionformat,FunctionCallcall,ExprformatString,DataFlow::Nodesinkwherecall.getTarget()=formatandcall.getArgument(format.getFormatParameterIndex())=formatStringandsink.asIndirectExpr(1)=formatStringandnotexists(DataFlow::Nodesource|DataFlow::localFlow(source,sink)andsource.asIndirectExpr(1)instanceofStringLiteral)selectcall,"Argument to "+format.getQualifiedName()+" isn't hard-coded."

Exercises

Exercise 1: Write a query that finds all hard-coded strings used to create ahost_ent viagethostbyname, using local data flow. (Answer)

Global data flow

Global data flow tracks data flow throughout the entire program, and is therefore more powerful than local data flow. However, global data flow is less precise than local data flow, and the analysis typically requires significantly more time and memory to perform.

Note

You can model data flow paths in CodeQL by creating path queries. To view data flow paths generated by a path query in CodeQL for VS Code, you need to make sure that it has the correct metadata andselect clause. For more information, seeCreating path queries.

Using global data flow

We can use the global data flow library by implementing the signatureDataFlow::ConfigSig and applying the moduleDataFlow::Global<ConfigSig>:

importsemmle.code.cpp.dataflow.new.DataFlowmoduleMyFlowConfigurationimplementsDataFlow::ConfigSig{predicateisSource(DataFlow::Nodesource){...}predicateisSink(DataFlow::Nodesink){...}}moduleMyFlow=DataFlow::Global<MyFlowConfiguration>;

The following predicates are defined in the configuration:

  • isSource—defines where data may flow from

  • isSink—defines where data may flow to

  • isBarrier—optional, restricts the data flow

  • isAdditionalFlowStep—optional, adds additional flow steps

The data flow analysis is performed using the predicateflow(DataFlow::Nodesource,DataFlow::Nodesink):

fromDataFlow::Nodesource,DataFlow::NodesinkwhereMyFlow::flow(source,sink)selectsource,"Data flow to $@.",sink,sink.toString()

Using global taint tracking

Global taint tracking is to global data flow as local taint tracking is to local data flow. That is, global taint tracking extends global data flow with additional non-value-preserving steps. The global taint tracking library is used by applying the moduleTaintTracking::Global<ConfigSig> to your configuration instead ofDataFlow::Global<ConfigSig> as follows:

importsemmle.code.cpp.dataflow.new.TaintTrackingmoduleMyFlowConfigurationimplementsDataFlow::ConfigSig{predicateisSource(DataFlow::Nodesource){...}predicateisSink(DataFlow::Nodesink){...}}moduleMyFlow=TaintTracking::Global<MyFlowConfiguration>;

The resulting module has an identical signature to the one obtained fromDataFlow::Global<ConfigSig>.

Examples

The following data flow configuration tracks data flow from environment variables to opening files in a Unix-like environment:

importcppimportsemmle.code.cpp.dataflow.new.DataFlowmoduleEnvironmentToFileConfigurationimplementsDataFlow::ConfigSig{predicateisSource(DataFlow::Nodesource){exists(Functiongetenv|source.asIndirectExpr(1).(FunctionCall).getTarget()=getenvandgetenv.hasGlobalName("getenv"))}predicateisSink(DataFlow::Nodesink){exists(FunctionCallfc|sink.asIndirectExpr(1)=fc.getArgument(0)andfc.getTarget().hasGlobalName("fopen"))}}moduleEnvironmentToFileFlow=DataFlow::Global<EnvironmentToFileConfiguration>;fromExprgetenv,Exprfopen,DataFlow::Nodesource,DataFlow::Nodesinkwheresource.asIndirectExpr(1)=getenvandsink.asIndirectExpr(1)=fopenandEnvironmentToFileFlow::flow(source,sink)selectfopen,"This 'fopen' uses data from $@.",getenv,"call to 'getenv'"

The following taint-tracking configuration tracks data from a call tontohl to an array index operation. It uses theGuards library to recognize expressions that have been bounds-checked, and definesisBarrier to prevent taint from propagating through them. It also usesisAdditionalFlowStep to add flow from loop bounds to loop indexes.

importcppimportsemmle.code.cpp.controlflow.Guardsimportsemmle.code.cpp.dataflow.new.TaintTrackingmoduleNetworkToBufferSizeConfigurationimplementsDataFlow::ConfigSig{predicateisSource(DataFlow::Nodenode){node.asExpr().(FunctionCall).getTarget().hasGlobalName("ntohl")}predicateisSink(DataFlow::Nodenode){exists(ArrayExprae|node.asExpr()=ae.getArrayOffset())}predicateisAdditionalFlowStep(DataFlow::Nodepred,DataFlow::Nodesucc){exists(Looploop,LoopCounterlc|loop=lc.getALoop()andloop.getControllingExpr().(RelationalOperation).getGreaterOperand()=pred.asExpr()|succ.asExpr()=lc.getVariableAccessInLoop(loop))}predicateisBarrier(DataFlow::Nodenode){exists(GuardConditiongc,Variablev|gc.getAChild*()=v.getAnAccess()andnode.asExpr()=v.getAnAccess()andgc.controls(node.asExpr().getBasicBlock(),_)andnotexists(Looploop|loop.getControllingExpr()=gc))}}moduleNetworkToBufferSizeFlow=TaintTracking::Global<NetworkToBufferSizeConfiguration>;fromDataFlow::Nodentohl,DataFlow::NodeoffsetwhereNetworkToBufferSizeFlow::flow(ntohl,offset)selectoffset,"This array offset may be influenced by $@.",ntohl,"converted data from the network"

Exercises

Exercise 2: Write a query that finds all hard-coded strings used to create ahost_ent viagethostbyname, using global data flow. (Answer)

Exercise 3: Write a class that represents flow sources fromgetenv. (Answer)

Exercise 4: Using the answers from 2 and 3, write a query which finds all global data flow paths fromgetenv togethostbyname. (Answer)

Answers

Exercise 1

importcppimportsemmle.code.cpp.dataflow.new.DataFlowfromStringLiteralsl,FunctionCallfc,DataFlow::Nodesource,DataFlow::Nodesinkwherefc.getTarget().hasName("gethostbyname")andsource.asIndirectExpr(1)=slandsink.asIndirectExpr(1)=fc.getArgument(0)andDataFlow::localFlow(source,sink)selectsl,fc

Exercise 2

importcppimportsemmle.code.cpp.dataflow.new.DataFlowmoduleLiteralToGethostbynameConfigurationimplementsDataFlow::ConfigSig{predicateisSource(DataFlow::Nodesource){source.asIndirectExpr(1)instanceofStringLiteral}predicateisSink(DataFlow::Nodesink){exists(FunctionCallfc|sink.asIndirectExpr(1)=fc.getArgument(0)andfc.getTarget().hasName("gethostbyname"))}}moduleLiteralToGethostbynameFlow=DataFlow::Global<LiteralToGethostbynameConfiguration>;fromStringLiteralsl,FunctionCallfc,DataFlow::Nodesource,DataFlow::Nodesinkwheresource.asIndirectExpr(1)=slandsink.asIndirectExpr(1)=fc.getArgument(0)andLiteralToGethostbynameFlow::flow(source,sink)selectsl,fc

Exercise 3

importcppimportsemmle.code.cpp.dataflow.new.DataFlowclassGetenvSourceextendsDataFlow::Node{GetenvSource(){this.asIndirectExpr(1).(FunctionCall).getTarget().hasGlobalName("getenv")}}

Exercise 4

importcppimportsemmle.code.cpp.dataflow.new.DataFlowclassGetenvSourceextendsDataFlow::Node{GetenvSource(){this.asIndirectExpr(1).(FunctionCall).getTarget().hasGlobalName("getenv")}}moduleGetenvToGethostbynameConfigurationimplementsDataFlow::ConfigSig{predicateisSource(DataFlow::Nodesource){sourceinstanceofGetenvSource}predicateisSink(DataFlow::Nodesink){exists(FunctionCallfc|sink.asIndirectExpr(1)=fc.getArgument(0)andfc.getTarget().hasName("gethostbyname"))}}moduleGetenvToGethostbynameFlow=DataFlow::Global<GetenvToGethostbynameConfiguration>;fromExprgetenv,FunctionCallfc,DataFlow::Nodesource,DataFlow::Nodesinkwheresource.asIndirectExpr(1)=getenvandsink.asIndirectExpr(1)=fc.getArgument(0)andGetenvToGethostbynameFlow::flow(source,sink)selectgetenv,fc

Further reading

[8]ページ先頭
©2009-2025 Movatter.jp