Compare commits

...

1 Commits

Author SHA1 Message Date
Edoardo Pirovano
33ea91042a Restore queries to old state 2022-11-04 10:09:46 +00:00
9853 changed files with 312424 additions and 871252 deletions

View File

@@ -4,6 +4,7 @@ provide:
- "*/ql/test/qlpack.yml"
- "*/ql/examples/qlpack.yml"
- "*/ql/consistency-queries/qlpack.yml"
- "*/upgrades/qlpack.yml"
- "shared/*/qlpack.yml"
- "cpp/ql/test/query-tests/Security/CWE/CWE-190/semmle/tainted/qlpack.yml"
- "go/ql/config/legacy-support/qlpack.yml"
@@ -25,9 +26,3 @@ provide:
- "ruby/extractor-pack/codeql-extractor.yml"
- "swift/extractor-pack/codeql-extractor.yml"
- "ql/extractor-pack/codeql-extractor.ym"
versionPolicies:
default:
requireChangeNotes: true
committedPrereleaseSuffix: dev
committedVersion: nextPatchRelease

View File

@@ -1,6 +1,4 @@
name: codeql/cpp-examples
groups:
- cpp
- examples
version: 0.0.2
dependencies:
codeql/cpp-all: ${workspace}
codeql/cpp-all: "*"

View File

@@ -1,15 +0,0 @@
package(default_visibility = ["//cpp:__pkg__"])
load("@rules_pkg//:mappings.bzl", "pkg_files")
pkg_files(
name = "dbscheme",
srcs = ["semmlecode.cpp.dbscheme"],
prefix = "cpp",
)
pkg_files(
name = "dbscheme-stats",
srcs = ["semmlecode.cpp.dbscheme.stats"],
prefix = "cpp",
)

View File

@@ -1,180 +0,0 @@
## 0.4.2
No user-facing changes.
## 0.4.1
No user-facing changes.
## 0.4.0
### Deprecated APIs
* Some classes/modules with upper-case acronyms in their name have been renamed to follow our style-guide.
The old name still exists as a deprecated alias.
### New Features
* Added subclasses of `BuiltInOperations` for `__is_same`, `__is_function`, `__is_layout_compatible`, `__is_pointer_interconvertible_base_of`, `__is_array`, `__array_rank`, `__array_extent`, `__is_arithmetic`, `__is_complete_type`, `__is_compound`, `__is_const`, `__is_floating_point`, `__is_fundamental`, `__is_integral`, `__is_lvalue_reference`, `__is_member_function_pointer`, `__is_member_object_pointer`, `__is_member_pointer`, `__is_object`, `__is_pointer`, `__is_reference`, `__is_rvalue_reference`, `__is_scalar`, `__is_signed`, `__is_unsigned`, `__is_void`, and `__is_volatile`.
### Bug Fixes
* Fixed an issue in the taint tracking analysis where implicit reads were not allowed by default in sinks or additional taint steps that used flow states.
## 0.3.5
## 0.3.4
### Deprecated APIs
* Many classes/predicates/modules with upper-case acronyms in their name have been renamed to follow our style-guide.
The old name still exists as a deprecated alias.
### New Features
* Added support for getting the link targets of global and namespace variables.
* Added a `BlockAssignExpr` class, which models a `memcpy`-like operation used in compiler generated copy/move constructors and assignment operations.
### Minor Analysis Improvements
* All deprecated predicates/classes/modules that have been deprecated for over a year have been deleted.
## 0.3.3
### New Features
* Added a predicate `getValueConstant` to `AttributeArgument` that yields the argument value as an `Expr` when the value is a constant expression.
* A new class predicate `MustFlowConfiguration::allowInterproceduralFlow` has been added to the `semmle.code.cpp.ir.dataflow.MustFlow` library. The new predicate can be overridden to disable interprocedural flow.
* Added subclasses of `BuiltInOperations` for `__builtin_bit_cast`, `__builtin_shuffle`, `__has_unique_object_representations`, `__is_aggregate`, and `__is_assignable`.
### Major Analysis Improvements
* The IR dataflow library now includes flow through global variables. This enables new findings in many scenarios.
## 0.3.2
### Bug Fixes
* Under certain circumstances a variable declaration that is not also a definition could be associated with a `Variable` that did not have the definition as a `VariableDeclarationEntry`. This is now fixed, and a unique `Variable` will exist that has both the declaration and the definition as a `VariableDeclarationEntry`.
## 0.3.1
### Minor Analysis Improvements
* `AnalysedExpr::isNullCheck` and `AnalysedExpr::isValidCheck` have been updated to handle variable accesses on the left-hand side of the C++ logical "and", and variable declarations in conditions.
## 0.3.0
### Deprecated APIs
* The `BarrierGuard` class has been deprecated. Such barriers and sanitizers can now instead be created using the new `BarrierGuard` parameterized module.
### Bug Fixes
* `UserType.getADeclarationEntry()` now yields all forward declarations when the user type is a `class`, `struct`, or `union`.
## 0.2.3
### New Features
* An `isBraced` predicate was added to the `Initializer` class which holds when a C++ braced initializer was used in the initialization.
## 0.2.2
### Deprecated APIs
* The `AnalysedString` class in the `StringAnalysis` module has been replaced with `AnalyzedString`, to follow our style guide. The old name still exists as a deprecated alias.
### New Features
* A `getInitialization` predicate was added to the `ConstexprIfStmt`, `IfStmt`, and `SwitchStmt` classes that yields the C++17-style initializer of the `if` or `switch` statement when it exists.
## 0.2.1
## 0.2.0
### Breaking Changes
* The signature of `allowImplicitRead` on `DataFlow::Configuration` and `TaintTracking::Configuration` has changed from `allowImplicitRead(DataFlow::Node node, DataFlow::Content c)` to `allowImplicitRead(DataFlow::Node node, DataFlow::ContentSet c)`.
### Minor Analysis Improvements
* More Windows pool allocation functions are now detected as `AllocationFunction`s.
* The `semmle.code.cpp.commons.Buffer` library has been enhanced to handle array members of classes that do not specify a size.
## 0.1.0
### Breaking Changes
* The recently added flow-state versions of `isBarrierIn`, `isBarrierOut`, `isSanitizerIn`, and `isSanitizerOut` in the data flow and taint tracking libraries have been removed.
### New Features
* A new library `semmle.code.cpp.security.PrivateData` has been added. The new library heuristically detects variables and functions dealing with sensitive private data, such as e-mail addresses and credit card numbers.
### Minor Analysis Improvements
* The `semmle.code.cpp.security.SensitiveExprs` library has been enhanced with some additional rules for detecting credentials.
## 0.0.13
## 0.0.12
### Breaking Changes
* The flow state variants of `isBarrier` and `isAdditionalFlowStep` are no longer exposed in the taint tracking library. The `isSanitizer` and `isAdditionalTaintStep` predicates should be used instead.
### Deprecated APIs
* Many classes/predicates/modules that had upper-case acronyms have been renamed to follow our style-guide.
The old name still exists as a deprecated alias.
### New Features
* The data flow and taint tracking libraries have been extended with versions of `isBarrierIn`, `isBarrierOut`, and `isBarrierGuard`, respectively `isSanitizerIn`, `isSanitizerOut`, and `isSanitizerGuard`, that support flow states.
### Minor Analysis Improvements
* `DefaultOptions::exits` now holds for C11 functions with the `_Noreturn` or `noreturn` specifier.
* `hasImplicitCopyConstructor` and `hasImplicitCopyAssignmentOperator` now correctly handle implicitly-deleted operators in templates.
* All deprecated predicates/classes/modules that have been deprecated for over a year have been deleted.
## 0.0.11
### Minor Analysis Improvements
* Many queries now support structured bindings, as structured bindings are now handled in the IR translation.
## 0.0.10
### New Features
* Added a `isStructuredBinding` predicate to the `Variable` class which holds when the variable is declared as part of a structured binding declaration.
## 0.0.9
## 0.0.8
### Deprecated APIs
* The `codeql/cpp-upgrades` CodeQL pack has been removed. All upgrades scripts have been merged into the `codeql/cpp-all` CodeQL pack.
### Minor Analysis Improvements
* `FormatLiteral::getMaxConvertedLength` now uses range analysis to provide a
more accurate length for integers formatted with `%x`
## 0.0.7
## 0.0.6
## 0.0.5
## 0.0.4
### New Features
* The QL library `semmle.code.cpp.commons.Exclusions` now contains a predicate
`isFromSystemMacroDefinition` for identifying code that originates from a
macro outside the project being analyzed.

View File

@@ -54,13 +54,11 @@ class Options extends string {
*
* By default, this holds for `exit`, `_exit`, `abort`, `__assert_fail`,
* `longjmp`, `__builtin_unreachable` and any function with a
* `noreturn` attribute or specifier.
* `noreturn` attribute.
*/
predicate exits(Function f) {
f.getAnAttribute().hasName("noreturn")
or
f.getASpecifier().hasName("noreturn")
or
f.hasGlobalOrStdName([
"exit", "_exit", "abort", "__assert_fail", "longjmp", "__builtin_unreachable"
])
@@ -75,7 +73,7 @@ class Options extends string {
* __assume(0);
* ```
* (note that in this case if the hint is wrong and the expression is reached at
* runtime, the program's behavior is undefined)
* runtime, the program's behaviour is undefined)
*/
predicate exprExits(Expr e) {
e.(AssumeExpr).getChild(0).(CompileTimeConstantInt).getIntValue() = 0 or

View File

@@ -39,7 +39,7 @@ class CustomOptions extends Options {
*
* By default, this holds for `exit`, `_exit`, `abort`, `__assert_fail`,
* `longjmp`, `error`, `__builtin_unreachable` and any function with a
* `noreturn` attribute or specifier.
* `noreturn` attribute.
*/
override predicate exits(Function f) { Options.super.exits(f) }
@@ -50,7 +50,7 @@ class CustomOptions extends Options {
* __assume(0);
* ```
* (note that in this case if the hint is wrong and the expression is reached at
* runtime, the program's behavior is undefined)
* runtime, the program's behaviour is undefined)
*/
override predicate exprExits(Expr e) { Options.super.exprExits(e) }

View File

@@ -1,4 +0,0 @@
---
category: minorAnalysis
---
* Fixed bugs in the `FormatLiteral` class that were causing `getMaxConvertedLength` and related predicates to return no results when the format literal was `%e`, `%f` or `%g` and an explicit precision was specified.

View File

@@ -1,5 +0,0 @@
## 0.0.10
### New Features
* Added a `isStructuredBinding` predicate to the `Variable` class which holds when the variable is declared as part of a structured binding declaration.

View File

@@ -1,5 +0,0 @@
## 0.0.11
### Minor Analysis Improvements
* Many queries now support structured bindings, as structured bindings are now handled in the IR translation.

View File

@@ -1,20 +0,0 @@
## 0.0.12
### Breaking Changes
* The flow state variants of `isBarrier` and `isAdditionalFlowStep` are no longer exposed in the taint tracking library. The `isSanitizer` and `isAdditionalTaintStep` predicates should be used instead.
### Deprecated APIs
* Many classes/predicates/modules that had upper-case acronyms have been renamed to follow our style-guide.
The old name still exists as a deprecated alias.
### New Features
* The data flow and taint tracking libraries have been extended with versions of `isBarrierIn`, `isBarrierOut`, and `isBarrierGuard`, respectively `isSanitizerIn`, `isSanitizerOut`, and `isSanitizerGuard`, that support flow states.
### Minor Analysis Improvements
* `DefaultOptions::exits` now holds for C11 functions with the `_Noreturn` or `noreturn` specifier.
* `hasImplicitCopyConstructor` and `hasImplicitCopyAssignmentOperator` now correctly handle implicitly-deleted operators in templates.
* All deprecated predicates/classes/modules that have been deprecated for over a year have been deleted.

View File

@@ -1 +0,0 @@
## 0.0.13

View File

@@ -1,7 +0,0 @@
## 0.0.4
### New Features
* The QL library `semmle.code.cpp.commons.Exclusions` now contains a predicate
`isFromSystemMacroDefinition` for identifying code that originates from a
macro outside the project being analyzed.

View File

@@ -1 +0,0 @@
## 0.0.5

View File

@@ -1 +0,0 @@
## 0.0.6

View File

@@ -1 +0,0 @@
## 0.0.7

View File

@@ -1,10 +0,0 @@
## 0.0.8
### Deprecated APIs
* The `codeql/cpp-upgrades` CodeQL pack has been removed. All upgrades scripts have been merged into the `codeql/cpp-all` CodeQL pack.
### Minor Analysis Improvements
* `FormatLiteral::getMaxConvertedLength` now uses range analysis to provide a
more accurate length for integers formatted with `%x`

View File

@@ -1,2 +0,0 @@
## 0.0.9

View File

@@ -1,13 +0,0 @@
## 0.1.0
### Breaking Changes
* The recently added flow-state versions of `isBarrierIn`, `isBarrierOut`, `isSanitizerIn`, and `isSanitizerOut` in the data flow and taint tracking libraries have been removed.
### New Features
* A new library `semmle.code.cpp.security.PrivateData` has been added. The new library heuristically detects variables and functions dealing with sensitive private data, such as e-mail addresses and credit card numbers.
### Minor Analysis Improvements
* The `semmle.code.cpp.security.SensitiveExprs` library has been enhanced with some additional rules for detecting credentials.

View File

@@ -1,10 +0,0 @@
## 0.2.0
### Breaking Changes
* The signature of `allowImplicitRead` on `DataFlow::Configuration` and `TaintTracking::Configuration` has changed from `allowImplicitRead(DataFlow::Node node, DataFlow::Content c)` to `allowImplicitRead(DataFlow::Node node, DataFlow::ContentSet c)`.
### Minor Analysis Improvements
* More Windows pool allocation functions are now detected as `AllocationFunction`s.
* The `semmle.code.cpp.commons.Buffer` library has been enhanced to handle array members of classes that do not specify a size.

View File

@@ -1 +0,0 @@
## 0.2.1

View File

@@ -1,9 +0,0 @@
## 0.2.2
### Deprecated APIs
* The `AnalysedString` class in the `StringAnalysis` module has been replaced with `AnalyzedString`, to follow our style guide. The old name still exists as a deprecated alias.
### New Features
* A `getInitialization` predicate was added to the `ConstexprIfStmt`, `IfStmt`, and `SwitchStmt` classes that yields the C++17-style initializer of the `if` or `switch` statement when it exists.

View File

@@ -1,5 +0,0 @@
## 0.2.3
### New Features
* An `isBraced` predicate was added to the `Initializer` class which holds when a C++ braced initializer was used in the initialization.

View File

@@ -1,9 +0,0 @@
## 0.3.0
### Deprecated APIs
* The `BarrierGuard` class has been deprecated. Such barriers and sanitizers can now instead be created using the new `BarrierGuard` parameterized module.
### Bug Fixes
* `UserType.getADeclarationEntry()` now yields all forward declarations when the user type is a `class`, `struct`, or `union`.

View File

@@ -1,5 +0,0 @@
## 0.3.1
### Minor Analysis Improvements
* `AnalysedExpr::isNullCheck` and `AnalysedExpr::isValidCheck` have been updated to handle variable accesses on the left-hand side of the C++ logical "and", and variable declarations in conditions.

View File

@@ -1,5 +0,0 @@
## 0.3.2
### Bug Fixes
* Under certain circumstances a variable declaration that is not also a definition could be associated with a `Variable` that did not have the definition as a `VariableDeclarationEntry`. This is now fixed, and a unique `Variable` will exist that has both the declaration and the definition as a `VariableDeclarationEntry`.

View File

@@ -1,11 +0,0 @@
## 0.3.3
### New Features
* Added a predicate `getValueConstant` to `AttributeArgument` that yields the argument value as an `Expr` when the value is a constant expression.
* A new class predicate `MustFlowConfiguration::allowInterproceduralFlow` has been added to the `semmle.code.cpp.ir.dataflow.MustFlow` library. The new predicate can be overridden to disable interprocedural flow.
* Added subclasses of `BuiltInOperations` for `__builtin_bit_cast`, `__builtin_shuffle`, `__has_unique_object_representations`, `__is_aggregate`, and `__is_assignable`.
### Major Analysis Improvements
* The IR dataflow library now includes flow through global variables. This enables new findings in many scenarios.

View File

@@ -1,15 +0,0 @@
## 0.3.4
### Deprecated APIs
* Many classes/predicates/modules with upper-case acronyms in their name have been renamed to follow our style-guide.
The old name still exists as a deprecated alias.
### New Features
* Added support for getting the link targets of global and namespace variables.
* Added a `BlockAssignExpr` class, which models a `memcpy`-like operation used in compiler generated copy/move constructors and assignment operations.
### Minor Analysis Improvements
* All deprecated predicates/classes/modules that have been deprecated for over a year have been deleted.

View File

@@ -1 +0,0 @@
## 0.3.5

View File

@@ -1,14 +0,0 @@
## 0.4.0
### Deprecated APIs
* Some classes/modules with upper-case acronyms in their name have been renamed to follow our style-guide.
The old name still exists as a deprecated alias.
### New Features
* Added subclasses of `BuiltInOperations` for `__is_same`, `__is_function`, `__is_layout_compatible`, `__is_pointer_interconvertible_base_of`, `__is_array`, `__array_rank`, `__array_extent`, `__is_arithmetic`, `__is_complete_type`, `__is_compound`, `__is_const`, `__is_floating_point`, `__is_fundamental`, `__is_integral`, `__is_lvalue_reference`, `__is_member_function_pointer`, `__is_member_object_pointer`, `__is_member_pointer`, `__is_object`, `__is_pointer`, `__is_reference`, `__is_rvalue_reference`, `__is_scalar`, `__is_signed`, `__is_unsigned`, `__is_void`, and `__is_volatile`.
### Bug Fixes
* Fixed an issue in the taint tracking analysis where implicit reads were not allowed by default in sinks or additional taint steps that used flow states.

View File

@@ -1,3 +0,0 @@
## 0.4.1
No user-facing changes.

View File

@@ -1,3 +0,0 @@
## 0.4.2
No user-facing changes.

View File

@@ -1,2 +0,0 @@
---
lastReleaseVersion: 0.4.2

View File

@@ -69,4 +69,6 @@ import semmle.code.cpp.Comments
import semmle.code.cpp.Preprocessor
import semmle.code.cpp.Iteration
import semmle.code.cpp.NameQualifiers
import semmle.code.cpp.ObjectiveC
import semmle.code.cpp.exprs.ObjectiveC
import DefaultOptions

View File

@@ -1,301 +0,0 @@
import experimental.semmle.code.cpp.ir.dataflow.DataFlow
import experimental.semmle.code.cpp.ir.dataflow.DataFlow2
module ProductFlow {
abstract class Configuration extends string {
bindingset[this]
Configuration() { any() }
/**
* Holds if `(source1, source2)` is a relevant data flow source.
*
* `source1` and `source2` must belong to the same callable.
*/
predicate isSourcePair(DataFlow::Node source1, DataFlow::Node source2) { none() }
/**
* Holds if `(source1, source2)` is a relevant data flow source with initial states `state1`
* and `state2`, respectively.
*
* `source1` and `source2` must belong to the same callable.
*/
predicate isSourcePair(
DataFlow::Node source1, DataFlow::FlowState state1, DataFlow::Node source2,
DataFlow::FlowState state2
) {
state1 = "" and
state2 = "" and
this.isSourcePair(source1, source2)
}
/**
* Holds if `(sink1, sink2)` is a relevant data flow sink.
*
* `sink1` and `sink2` must belong to the same callable.
*/
predicate isSinkPair(DataFlow::Node sink1, DataFlow::Node sink2) { none() }
/**
* Holds if `(sink1, sink2)` is a relevant data flow sink with final states `state1`
* and `state2`, respectively.
*
* `sink1` and `sink2` must belong to the same callable.
*/
predicate isSinkPair(
DataFlow::Node sink1, DataFlow::FlowState state1, DataFlow::Node sink2,
DataFlow::FlowState state2
) {
state1 = "" and
state2 = "" and
this.isSinkPair(sink1, sink2)
}
/**
* Holds if data flow through `node` is prohibited through the first projection of the product
* dataflow graph when the flow state is `state`.
*/
predicate isBarrier1(DataFlow::Node node, DataFlow::FlowState state) {
this.isBarrier1(node) and state = ""
}
/**
* Holds if data flow through `node` is prohibited through the second projection of the product
* dataflow graph when the flow state is `state`.
*/
predicate isBarrier2(DataFlow::Node node, DataFlow::FlowState state) {
this.isBarrier2(node) and state = ""
}
/**
* Holds if data flow through `node` is prohibited through the first projection of the product
* dataflow graph.
*/
predicate isBarrier1(DataFlow::Node node) { none() }
/**
* Holds if data flow through `node` is prohibited through the second projection of the product
* dataflow graph.
*/
predicate isBarrier2(DataFlow::Node node) { none() }
/**
* Holds if data flow out of `node` is prohibited in the first projection of the product
* dataflow graph.
*/
predicate isBarrierOut1(DataFlow::Node node) { none() }
/**
* Holds if data flow out of `node` is prohibited in the second projection of the product
* dataflow graph.
*/
predicate isBarrierOut2(DataFlow::Node node) { none() }
/*
* Holds if data may flow from `node1` to `node2` in addition to the normal data-flow steps in
* the first projection of the product dataflow graph.
*/
predicate isAdditionalFlowStep1(DataFlow::Node node1, DataFlow::Node node2) { none() }
/**
* Holds if data may flow from `node1` to `node2` in addition to the normal data-flow steps in
* the first projection of the product dataflow graph.
*
* This step is only applicable in `state1` and updates the flow state to `state2`.
*/
predicate isAdditionalFlowStep1(
DataFlow::Node node1, DataFlow::FlowState state1, DataFlow::Node node2,
DataFlow::FlowState state2
) {
state1 instanceof DataFlow::FlowStateEmpty and
state2 instanceof DataFlow::FlowStateEmpty and
this.isAdditionalFlowStep1(node1, node2)
}
/**
* Holds if data may flow from `node1` to `node2` in addition to the normal data-flow steps in
* the second projection of the product dataflow graph.
*/
predicate isAdditionalFlowStep2(DataFlow::Node node1, DataFlow::Node node2) { none() }
/**
* Holds if data may flow from `node1` to `node2` in addition to the normal data-flow steps in
* the second projection of the product dataflow graph.
*
* This step is only applicable in `state1` and updates the flow state to `state2`.
*/
predicate isAdditionalFlowStep2(
DataFlow::Node node1, DataFlow::FlowState state1, DataFlow::Node node2,
DataFlow::FlowState state2
) {
state1 instanceof DataFlow::FlowStateEmpty and
state2 instanceof DataFlow::FlowStateEmpty and
this.isAdditionalFlowStep2(node1, node2)
}
/**
* Holds if data flow into `node` is prohibited in the first projection of the product
* dataflow graph.
*/
predicate isBarrierIn1(DataFlow::Node node) { none() }
/**
* Holds if data flow into `node` is prohibited in the second projection of the product
* dataflow graph.
*/
predicate isBarrierIn2(DataFlow::Node node) { none() }
predicate hasFlowPath(
DataFlow::PathNode source1, DataFlow2::PathNode source2, DataFlow::PathNode sink1,
DataFlow2::PathNode sink2
) {
reachable(this, source1, source2, sink1, sink2)
}
}
private import Internal
module Internal {
class Conf1 extends DataFlow::Configuration {
Conf1() { this = "Conf1" }
override predicate isSource(DataFlow::Node source, DataFlow::FlowState state) {
exists(Configuration conf | conf.isSourcePair(source, state, _, _))
}
override predicate isSink(DataFlow::Node sink, DataFlow::FlowState state) {
exists(Configuration conf | conf.isSinkPair(sink, state, _, _))
}
override predicate isBarrier(DataFlow::Node node, DataFlow::FlowState state) {
exists(Configuration conf | conf.isBarrier1(node, state))
}
override predicate isBarrierOut(DataFlow::Node node) {
exists(Configuration conf | conf.isBarrierOut1(node))
}
override predicate isAdditionalFlowStep(
DataFlow::Node node1, DataFlow::FlowState state1, DataFlow::Node node2,
DataFlow::FlowState state2
) {
exists(Configuration conf | conf.isAdditionalFlowStep1(node1, state1, node2, state2))
}
override predicate isBarrierIn(DataFlow::Node node) {
exists(Configuration conf | conf.isBarrierIn1(node))
}
}
class Conf2 extends DataFlow2::Configuration {
Conf2() { this = "Conf2" }
override predicate isSource(DataFlow::Node source, DataFlow::FlowState state) {
exists(Configuration conf, DataFlow::PathNode source1 |
conf.isSourcePair(source1.getNode(), source1.getState(), source, state) and
any(Conf1 c).hasFlowPath(source1, _)
)
}
override predicate isSink(DataFlow::Node sink, DataFlow::FlowState state) {
exists(Configuration conf, DataFlow::PathNode sink1 |
conf.isSinkPair(sink1.getNode(), sink1.getState(), sink, state) and
any(Conf1 c).hasFlowPath(_, sink1)
)
}
override predicate isBarrier(DataFlow::Node node, DataFlow::FlowState state) {
exists(Configuration conf | conf.isBarrier2(node, state))
}
override predicate isBarrierOut(DataFlow::Node node) {
exists(Configuration conf | conf.isBarrierOut2(node))
}
override predicate isAdditionalFlowStep(
DataFlow::Node node1, DataFlow::FlowState state1, DataFlow::Node node2,
DataFlow::FlowState state2
) {
exists(Configuration conf | conf.isAdditionalFlowStep2(node1, state1, node2, state2))
}
override predicate isBarrierIn(DataFlow::Node node) {
exists(Configuration conf | conf.isBarrierIn2(node))
}
}
}
pragma[nomagic]
private predicate reachableInterprocEntry(
Configuration conf, DataFlow::PathNode source1, DataFlow2::PathNode source2,
DataFlow::PathNode node1, DataFlow2::PathNode node2
) {
conf.isSourcePair(node1.getNode(), node1.getState(), node2.getNode(), node2.getState()) and
node1 = source1 and
node2 = source2
or
exists(
DataFlow::PathNode midEntry1, DataFlow2::PathNode midEntry2, DataFlow::PathNode midExit1,
DataFlow2::PathNode midExit2
|
reachableInterprocEntry(conf, source1, source2, midEntry1, midEntry2) and
interprocEdgePair(midExit1, midExit2, node1, node2) and
localPathStep1*(midEntry1, midExit1) and
localPathStep2*(midEntry2, midExit2)
)
}
private predicate localPathStep1(DataFlow::PathNode pred, DataFlow::PathNode succ) {
DataFlow::PathGraph::edges(pred, succ) and
pragma[only_bind_out](pred.getNode().getEnclosingCallable()) =
pragma[only_bind_out](succ.getNode().getEnclosingCallable())
}
private predicate localPathStep2(DataFlow2::PathNode pred, DataFlow2::PathNode succ) {
DataFlow2::PathGraph::edges(pred, succ) and
pragma[only_bind_out](pred.getNode().getEnclosingCallable()) =
pragma[only_bind_out](succ.getNode().getEnclosingCallable())
}
pragma[nomagic]
private predicate interprocEdge1(
Declaration predDecl, Declaration succDecl, DataFlow::PathNode pred1, DataFlow::PathNode succ1
) {
DataFlow::PathGraph::edges(pred1, succ1) and
predDecl != succDecl and
pred1.getNode().getEnclosingCallable() = predDecl and
succ1.getNode().getEnclosingCallable() = succDecl
}
pragma[nomagic]
private predicate interprocEdge2(
Declaration predDecl, Declaration succDecl, DataFlow2::PathNode pred2, DataFlow2::PathNode succ2
) {
DataFlow2::PathGraph::edges(pred2, succ2) and
predDecl != succDecl and
pred2.getNode().getEnclosingCallable() = predDecl and
succ2.getNode().getEnclosingCallable() = succDecl
}
private predicate interprocEdgePair(
DataFlow::PathNode pred1, DataFlow2::PathNode pred2, DataFlow::PathNode succ1,
DataFlow2::PathNode succ2
) {
exists(Declaration predDecl, Declaration succDecl |
interprocEdge1(predDecl, succDecl, pred1, succ1) and
interprocEdge2(predDecl, succDecl, pred2, succ2)
)
}
private predicate reachable(
Configuration conf, DataFlow::PathNode source1, DataFlow2::PathNode source2,
DataFlow::PathNode sink1, DataFlow2::PathNode sink2
) {
exists(DataFlow::PathNode mid1, DataFlow2::PathNode mid2 |
reachableInterprocEntry(conf, source1, source2, mid1, mid2) and
conf.isSinkPair(sink1.getNode(), sink1.getState(), sink2.getNode(), sink2.getState()) and
localPathStep1*(mid1, sink1) and
localPathStep2*(mid2, sink2)
)
}
}

View File

@@ -1,26 +0,0 @@
/**
* Provides a library for local (intra-procedural) and global (inter-procedural)
* data flow analysis: deciding whether data can flow from a _source_ to a
* _sink_. This library differs from the one in `semmle.code.cpp.dataflow` in that
* this library uses the IR (Intermediate Representation) library, which provides
* a more precise semantic representation of the program, whereas the other dataflow
* library uses the more syntax-oriented ASTs. This library should provide more accurate
* results than the AST-based library in most scenarios.
*
* Unless configured otherwise, _flow_ means that the exact value of
* the source may reach the sink. We do not track flow across pointer
* dereferences or array indexing.
*
* To use global (interprocedural) data flow, extend the class
* `DataFlow::Configuration` as documented on that class. To use local
* (intraprocedural) data flow between expressions, call
* `DataFlow::localExprFlow`. For more general cases of local data flow, call
* `DataFlow::localFlow` or `DataFlow::localFlowStep` with arguments of type
* `DataFlow::Node`.
*/
import cpp
module DataFlow {
import experimental.semmle.code.cpp.ir.dataflow.internal.DataFlowImpl
}

View File

@@ -1,16 +0,0 @@
/**
* Provides a `DataFlow2` module, which is a copy of the `DataFlow` module. Use
* this class when data-flow configurations must depend on each other. Two
* classes extending `DataFlow::Configuration` should never depend on each
* other, but one of them should instead depend on a
* `DataFlow2::Configuration`, a `DataFlow3::Configuration`, or a
* `DataFlow4::Configuration`.
*
* See `semmle.code.cpp.ir.dataflow.DataFlow` for the full documentation.
*/
import cpp
module DataFlow2 {
import experimental.semmle.code.cpp.ir.dataflow.internal.DataFlowImpl2
}

View File

@@ -1,16 +0,0 @@
/**
* Provides a `DataFlow3` module, which is a copy of the `DataFlow` module. Use
* this class when data-flow configurations must depend on each other. Two
* classes extending `DataFlow::Configuration` should never depend on each
* other, but one of them should instead depend on a
* `DataFlow2::Configuration`, a `DataFlow3::Configuration`, or a
* `DataFlow4::Configuration`.
*
* See `semmle.code.cpp.ir.dataflow.DataFlow` for the full documentation.
*/
import cpp
module DataFlow3 {
import experimental.semmle.code.cpp.ir.dataflow.internal.DataFlowImpl3
}

View File

@@ -1,16 +0,0 @@
/**
* Provides a `DataFlow4` module, which is a copy of the `DataFlow` module. Use
* this class when data-flow configurations must depend on each other. Two
* classes extending `DataFlow::Configuration` should never depend on each
* other, but one of them should instead depend on a
* `DataFlow2::Configuration`, a `DataFlow3::Configuration`, or a
* `DataFlow4::Configuration`.
*
* See `semmle.code.cpp.ir.dataflow.DataFlow` for the full documentation.
*/
import cpp
module DataFlow4 {
import experimental.semmle.code.cpp.ir.dataflow.internal.DataFlowImpl4
}

View File

@@ -1,23 +0,0 @@
/**
* Provides a predicate for non-contextual virtual dispatch and function
* pointer resolution.
*/
import cpp
private import semmle.code.cpp.ir.ValueNumbering
private import internal.DataFlowDispatch
private import semmle.code.cpp.ir.IR
/**
* Resolve potential target function(s) for `call`.
*
* If `call` is a call through a function pointer (`ExprCall`) or its target is
* a virtual member function, simple data flow analysis is performed in order
* to identify the possible target(s).
*/
Function resolveCall(Call call) {
exists(CallInstruction callInstruction |
callInstruction.getAst() = call and
result = viableCallable(callInstruction)
)
}

View File

@@ -1,23 +0,0 @@
/**
* Provides classes for performing local (intra-procedural) and
* global (inter-procedural) taint-tracking analyses.
*
* We define _taint propagation_ informally to mean that a substantial part of
* the information from the source is preserved at the sink. For example, taint
* propagates from `x` to `x + 100`, but it does not propagate from `x` to `x >
* 100` since we consider a single bit of information to be too little.
*
* To use global (interprocedural) taint tracking, extend the class
* `TaintTracking::Configuration` as documented on that class. To use local
* (intraprocedural) taint tracking between expressions, call
* `TaintTracking::localExprTaint`. For more general cases of local taint
* tracking, call `TaintTracking::localTaint` or
* `TaintTracking::localTaintStep` with arguments of type `DataFlow::Node`.
*/
import semmle.code.cpp.ir.dataflow.DataFlow
import semmle.code.cpp.ir.dataflow.DataFlow2
module TaintTracking {
import experimental.semmle.code.cpp.ir.dataflow.internal.tainttracking1.TaintTrackingImpl
}

View File

@@ -1,15 +0,0 @@
/**
* Provides a `TaintTracking2` module, which is a copy of the `TaintTracking`
* module. Use this class when data-flow configurations or taint-tracking
* configurations must depend on each other. Two classes extending
* `DataFlow::Configuration` should never depend on each other, but one of them
* should instead depend on a `DataFlow2::Configuration`, a
* `DataFlow3::Configuration`, or a `DataFlow4::Configuration`. The
* `TaintTracking::Configuration` class extends `DataFlow::Configuration`, and
* `TaintTracking2::Configuration` extends `DataFlow2::Configuration`.
*
* See `semmle.code.cpp.ir.dataflow.TaintTracking` for the full documentation.
*/
module TaintTracking2 {
import experimental.semmle.code.cpp.ir.dataflow.internal.tainttracking2.TaintTrackingImpl
}

View File

@@ -1,15 +0,0 @@
/**
* Provides a `TaintTracking3` module, which is a copy of the `TaintTracking`
* module. Use this class when data-flow configurations or taint-tracking
* configurations must depend on each other. Two classes extending
* `DataFlow::Configuration` should never depend on each other, but one of them
* should instead depend on a `DataFlow2::Configuration`, a
* `DataFlow3::Configuration`, or a `DataFlow4::Configuration`. The
* `TaintTracking::Configuration` class extends `DataFlow::Configuration`, and
* `TaintTracking2::Configuration` extends `DataFlow2::Configuration`.
*
* See `semmle.code.cpp.ir.dataflow.TaintTracking` for the full documentation.
*/
module TaintTracking3 {
import experimental.semmle.code.cpp.ir.dataflow.internal.tainttracking3.TaintTrackingImpl
}

View File

@@ -1,273 +0,0 @@
private import cpp
private import semmle.code.cpp.ir.IR
private import experimental.semmle.code.cpp.ir.dataflow.DataFlow
private import experimental.semmle.code.cpp.ir.dataflow.internal.DataFlowPrivate
private import experimental.semmle.code.cpp.ir.dataflow.internal.DataFlowUtil
private import DataFlowImplCommon as DataFlowImplCommon
/**
* Gets a function that might be called by `call`.
*/
cached
Function viableCallable(CallInstruction call) {
DataFlowImplCommon::forceCachingInSameStage() and
result = call.getStaticCallTarget()
or
// If the target of the call does not have a body in the snapshot, it might
// be because the target is just a header declaration, and the real target
// will be determined at run time when the caller and callee are linked
// together by the operating system's dynamic linker. In case a _unique_
// function with the right signature is present in the database, we return
// that as a potential callee.
exists(string qualifiedName, int nparams |
callSignatureWithoutBody(qualifiedName, nparams, call) and
functionSignatureWithBody(qualifiedName, nparams, result) and
strictcount(Function other | functionSignatureWithBody(qualifiedName, nparams, other)) = 1
)
or
// Virtual dispatch
result = call.(VirtualDispatch::DataSensitiveCall).resolve()
}
/**
* Provides virtual dispatch support compatible with the original
* implementation of `semmle.code.cpp.security.TaintTracking`.
*/
private module VirtualDispatch {
/** A call that may dispatch differently depending on the qualifier value. */
abstract class DataSensitiveCall extends DataFlowCall {
/**
* Gets the node whose value determines the target of this call. This node
* could be the qualifier of a virtual dispatch or the function-pointer
* expression in a call to a function pointer. What they have in common is
* that we need to find out which data flows there, and then it's up to the
* `resolve` predicate to stitch that information together and resolve the
* call.
*/
abstract DataFlow::Node getDispatchValue();
/** Gets a candidate target for this call. */
abstract Function resolve();
/**
* Whether `src` can flow to this call.
*
* Searches backwards from `getDispatchValue()` to `src`. The `allowFromArg`
* parameter is true when the search is allowed to continue backwards into
* a parameter; non-recursive callers should pass `_` for `allowFromArg`.
*/
predicate flowsFrom(DataFlow::Node src, boolean allowFromArg) {
src = this.getDispatchValue() and allowFromArg = true
or
exists(DataFlow::Node other, boolean allowOtherFromArg |
this.flowsFrom(other, allowOtherFromArg)
|
// Call argument
exists(DataFlowCall call, Position i |
other
.(DataFlow::ParameterNode)
.isParameterOf(pragma[only_bind_into](call).getStaticCallTarget(), i) and
src.(ArgumentNode).argumentOf(call, pragma[only_bind_into](pragma[only_bind_out](i)))
) and
allowOtherFromArg = true and
allowFromArg = true
or
// Call return
exists(DataFlowCall call, ReturnKind returnKind |
other = getAnOutNode(call, returnKind) and
returnNodeWithKindAndEnclosingCallable(src, returnKind, call.getStaticCallTarget())
) and
allowFromArg = false
or
// Local flow
DataFlow::localFlowStep(src, other) and
allowFromArg = allowOtherFromArg
or
// Flow from global variable to load.
exists(LoadInstruction load, GlobalOrNamespaceVariable var |
var = src.asVariable() and
other.asInstruction() = load and
addressOfGlobal(load.getSourceAddress(), var) and
// The `allowFromArg` concept doesn't play a role when `src` is a
// global variable, so we just set it to a single arbitrary value for
// performance.
allowFromArg = true
)
or
// Flow from store to global variable.
exists(StoreInstruction store, GlobalOrNamespaceVariable var |
var = other.asVariable() and
store = src.asInstruction() and
storeIntoGlobal(store, var) and
// Setting `allowFromArg` to `true` like in the base case means we
// treat a store to a global variable like the dispatch itself: flow
// may come from anywhere.
allowFromArg = true
)
)
}
}
pragma[noinline]
private predicate storeIntoGlobal(StoreInstruction store, GlobalOrNamespaceVariable var) {
addressOfGlobal(store.getDestinationAddress(), var)
}
/** Holds if `addressInstr` is an instruction that produces the address of `var`. */
private predicate addressOfGlobal(Instruction addressInstr, GlobalOrNamespaceVariable var) {
// Access directly to the global variable
addressInstr.(VariableAddressInstruction).getAstVariable() = var
or
// Access to a field on a global union
exists(FieldAddressInstruction fa |
fa = addressInstr and
fa.getObjectAddress().(VariableAddressInstruction).getAstVariable() = var and
fa.getField().getDeclaringType() instanceof Union
)
}
/**
* A ReturnNode with its ReturnKind and its enclosing callable.
*
* Used to fix a join ordering issue in flowsFrom.
*/
pragma[noinline]
private predicate returnNodeWithKindAndEnclosingCallable(
ReturnNode node, ReturnKind kind, DataFlowCallable callable
) {
node.getKind() = kind and
node.getEnclosingCallable() = callable
}
/** Call through a function pointer. */
private class DataSensitiveExprCall extends DataSensitiveCall {
DataSensitiveExprCall() { not exists(this.getStaticCallTarget()) }
override DataFlow::Node getDispatchValue() { result.asInstruction() = this.getCallTarget() }
override Function resolve() {
exists(FunctionInstruction fi |
this.flowsFrom(DataFlow::instructionNode(fi), _) and
result = fi.getFunctionSymbol()
) and
(
this.getNumberOfArguments() <= result.getEffectiveNumberOfParameters() and
this.getNumberOfArguments() >= result.getEffectiveNumberOfParameters()
or
result.isVarargs()
)
}
}
/** Call to a virtual function. */
private class DataSensitiveOverriddenFunctionCall extends DataSensitiveCall {
DataSensitiveOverriddenFunctionCall() {
exists(this.getStaticCallTarget().(VirtualFunction).getAnOverridingFunction())
}
override DataFlow::Node getDispatchValue() { result.asInstruction() = this.getThisArgument() }
override MemberFunction resolve() {
exists(Class overridingClass |
this.overrideMayAffectCall(overridingClass, result) and
this.hasFlowFromCastFrom(overridingClass)
)
}
/**
* Holds if `this` is a virtual function call whose static target is
* overridden by `overridingFunction` in `overridingClass`.
*/
pragma[noinline]
private predicate overrideMayAffectCall(Class overridingClass, MemberFunction overridingFunction) {
overridingFunction.getAnOverriddenFunction+() = this.getStaticCallTarget().(VirtualFunction) and
overridingFunction.getDeclaringType() = overridingClass
}
/**
* Holds if the qualifier of `this` has flow from an upcast from
* `derivedClass`.
*/
pragma[noinline]
private predicate hasFlowFromCastFrom(Class derivedClass) {
exists(ConvertToBaseInstruction toBase |
this.flowsFrom(DataFlow::instructionNode(toBase), _) and
derivedClass = toBase.getDerivedClass()
)
}
}
}
/**
* Holds if `f` is a function with a body that has name `qualifiedName` and
* `nparams` parameter count. See `functionSignature`.
*/
private predicate functionSignatureWithBody(string qualifiedName, int nparams, Function f) {
functionSignature(f, qualifiedName, nparams) and
exists(f.getBlock())
}
/**
* Holds if the target of `call` is a function _with no definition_ that has
* name `qualifiedName` and `nparams` parameter count. See `functionSignature`.
*/
pragma[noinline]
private predicate callSignatureWithoutBody(string qualifiedName, int nparams, CallInstruction call) {
exists(Function target |
target = call.getStaticCallTarget() and
not exists(target.getBlock()) and
functionSignature(target, qualifiedName, nparams)
)
}
/**
* Holds if `f` has name `qualifiedName` and `nparams` parameter count. This is
* an approximation of its signature for the purpose of matching functions that
* might be the same across link targets.
*/
private predicate functionSignature(Function f, string qualifiedName, int nparams) {
qualifiedName = f.getQualifiedName() and
nparams = f.getNumberOfParameters() and
not f.isStatic()
}
/**
* Holds if the set of viable implementations that can be called by `call`
* might be improved by knowing the call context.
*/
predicate mayBenefitFromCallContext(CallInstruction call, Function f) {
mayBenefitFromCallContext(call, f, _)
}
/**
* Holds if `call` is a call through a function pointer, and the pointer
* value is given as the `arg`'th argument to `f`.
*/
private predicate mayBenefitFromCallContext(
VirtualDispatch::DataSensitiveCall call, Function f, int arg
) {
f = pragma[only_bind_out](call).getEnclosingCallable() and
exists(InitializeParameterInstruction init |
not exists(call.getStaticCallTarget()) and
init.getEnclosingFunction() = f and
call.flowsFrom(DataFlow::instructionNode(init), _) and
init.getParameter().getIndex() = arg
)
}
/**
* Gets a viable dispatch target of `call` in the context `ctx`. This is
* restricted to those `call`s for which a context might make a difference.
*/
Function viableImplInCallContext(CallInstruction call, CallInstruction ctx) {
result = viableCallable(call) and
exists(int i, Function f |
mayBenefitFromCallContext(pragma[only_bind_into](call), f, i) and
f = ctx.getStaticCallTarget() and
result = ctx.getArgument(i).getUnconvertedResultExpression().(FunctionAccess).getTarget()
)
}
/** Holds if arguments at position `apos` match parameters at position `ppos`. */
pragma[inline]
predicate parameterMatch(ParameterPosition ppos, ArgumentPosition apos) { ppos = apos }

View File

@@ -1,235 +0,0 @@
/**
* Provides consistency queries for checking invariants in the language-specific
* data-flow classes and predicates.
*/
private import DataFlowImplSpecific::Private
private import DataFlowImplSpecific::Public
private import tainttracking1.TaintTrackingParameter::Private
private import tainttracking1.TaintTrackingParameter::Public
module Consistency {
private newtype TConsistencyConfiguration = MkConsistencyConfiguration()
/** A class for configuring the consistency queries. */
class ConsistencyConfiguration extends TConsistencyConfiguration {
string toString() { none() }
/** Holds if `n` should be excluded from the consistency test `uniqueEnclosingCallable`. */
predicate uniqueEnclosingCallableExclude(Node n) { none() }
/** Holds if `n` should be excluded from the consistency test `uniqueNodeLocation`. */
predicate uniqueNodeLocationExclude(Node n) { none() }
/** Holds if `n` should be excluded from the consistency test `missingLocation`. */
predicate missingLocationExclude(Node n) { none() }
/** Holds if `n` should be excluded from the consistency test `postWithInFlow`. */
predicate postWithInFlowExclude(Node n) { none() }
/** Holds if `n` should be excluded from the consistency test `argHasPostUpdate`. */
predicate argHasPostUpdateExclude(ArgumentNode n) { none() }
/** Holds if `n` should be excluded from the consistency test `reverseRead`. */
predicate reverseReadExclude(Node n) { none() }
/** Holds if `n` should be excluded from the consistency test `postHasUniquePre`. */
predicate postHasUniquePreExclude(PostUpdateNode n) { none() }
/** Holds if `n` should be excluded from the consistency test `uniquePostUpdate`. */
predicate uniquePostUpdateExclude(Node n) { none() }
/** Holds if `(call, ctx)` should be excluded from the consistency test `viableImplInCallContextTooLargeExclude`. */
predicate viableImplInCallContextTooLargeExclude(
DataFlowCall call, DataFlowCall ctx, DataFlowCallable callable
) {
none()
}
}
private class RelevantNode extends Node {
RelevantNode() {
this instanceof ArgumentNode or
this instanceof ParameterNode or
this instanceof ReturnNode or
this = getAnOutNode(_, _) or
simpleLocalFlowStep(this, _) or
simpleLocalFlowStep(_, this) or
jumpStep(this, _) or
jumpStep(_, this) or
storeStep(this, _, _) or
storeStep(_, _, this) or
readStep(this, _, _) or
readStep(_, _, this) or
defaultAdditionalTaintStep(this, _) or
defaultAdditionalTaintStep(_, this)
}
}
query predicate uniqueEnclosingCallable(Node n, string msg) {
exists(int c |
n instanceof RelevantNode and
c = count(nodeGetEnclosingCallable(n)) and
c != 1 and
not any(ConsistencyConfiguration conf).uniqueEnclosingCallableExclude(n) and
msg = "Node should have one enclosing callable but has " + c + "."
)
}
query predicate uniqueType(Node n, string msg) {
exists(int c |
n instanceof RelevantNode and
c = count(getNodeType(n)) and
c != 1 and
msg = "Node should have one type but has " + c + "."
)
}
query predicate uniqueNodeLocation(Node n, string msg) {
exists(int c |
c =
count(string filepath, int startline, int startcolumn, int endline, int endcolumn |
n.hasLocationInfo(filepath, startline, startcolumn, endline, endcolumn)
) and
c != 1 and
not any(ConsistencyConfiguration conf).uniqueNodeLocationExclude(n) and
msg = "Node should have one location but has " + c + "."
)
}
query predicate missingLocation(string msg) {
exists(int c |
c =
strictcount(Node n |
not exists(string filepath, int startline, int startcolumn, int endline, int endcolumn |
n.hasLocationInfo(filepath, startline, startcolumn, endline, endcolumn)
) and
not any(ConsistencyConfiguration conf).missingLocationExclude(n)
) and
msg = "Nodes without location: " + c
)
}
query predicate uniqueNodeToString(Node n, string msg) {
exists(int c |
c = count(n.toString()) and
c != 1 and
msg = "Node should have one toString but has " + c + "."
)
}
query predicate missingToString(string msg) {
exists(int c |
c = strictcount(Node n | not exists(n.toString())) and
msg = "Nodes without toString: " + c
)
}
query predicate parameterCallable(ParameterNode p, string msg) {
exists(DataFlowCallable c | isParameterNode(p, c, _) and c != nodeGetEnclosingCallable(p)) and
msg = "Callable mismatch for parameter."
}
query predicate localFlowIsLocal(Node n1, Node n2, string msg) {
simpleLocalFlowStep(n1, n2) and
nodeGetEnclosingCallable(n1) != nodeGetEnclosingCallable(n2) and
msg = "Local flow step does not preserve enclosing callable."
}
private DataFlowType typeRepr() { result = getNodeType(_) }
query predicate compatibleTypesReflexive(DataFlowType t, string msg) {
t = typeRepr() and
not compatibleTypes(t, t) and
msg = "Type compatibility predicate is not reflexive."
}
query predicate unreachableNodeCCtx(Node n, DataFlowCall call, string msg) {
isUnreachableInCall(n, call) and
exists(DataFlowCallable c |
c = nodeGetEnclosingCallable(n) and
not viableCallable(call) = c
) and
msg = "Call context for isUnreachableInCall is inconsistent with call graph."
}
query predicate localCallNodes(DataFlowCall call, Node n, string msg) {
(
n = getAnOutNode(call, _) and
msg = "OutNode and call does not share enclosing callable."
or
n.(ArgumentNode).argumentOf(call, _) and
msg = "ArgumentNode and call does not share enclosing callable."
) and
nodeGetEnclosingCallable(n) != call.getEnclosingCallable()
}
// This predicate helps the compiler forget that in some languages
// it is impossible for a result of `getPreUpdateNode` to be an
// instance of `PostUpdateNode`.
private Node getPre(PostUpdateNode n) {
result = n.getPreUpdateNode()
or
none()
}
query predicate postIsNotPre(PostUpdateNode n, string msg) {
getPre(n) = n and
msg = "PostUpdateNode should not equal its pre-update node."
}
query predicate postHasUniquePre(PostUpdateNode n, string msg) {
not any(ConsistencyConfiguration conf).postHasUniquePreExclude(n) and
exists(int c |
c = count(n.getPreUpdateNode()) and
c != 1 and
msg = "PostUpdateNode should have one pre-update node but has " + c + "."
)
}
query predicate uniquePostUpdate(Node n, string msg) {
not any(ConsistencyConfiguration conf).uniquePostUpdateExclude(n) and
1 < strictcount(PostUpdateNode post | post.getPreUpdateNode() = n) and
msg = "Node has multiple PostUpdateNodes."
}
query predicate postIsInSameCallable(PostUpdateNode n, string msg) {
nodeGetEnclosingCallable(n) != nodeGetEnclosingCallable(n.getPreUpdateNode()) and
msg = "PostUpdateNode does not share callable with its pre-update node."
}
private predicate hasPost(Node n) { exists(PostUpdateNode post | post.getPreUpdateNode() = n) }
query predicate reverseRead(Node n, string msg) {
exists(Node n2 | readStep(n, _, n2) and hasPost(n2) and not hasPost(n)) and
not any(ConsistencyConfiguration conf).reverseReadExclude(n) and
msg = "Origin of readStep is missing a PostUpdateNode."
}
query predicate argHasPostUpdate(ArgumentNode n, string msg) {
not hasPost(n) and
not any(ConsistencyConfiguration c).argHasPostUpdateExclude(n) and
msg = "ArgumentNode is missing PostUpdateNode."
}
// This predicate helps the compiler forget that in some languages
// it is impossible for a `PostUpdateNode` to be the target of
// `simpleLocalFlowStep`.
private predicate isPostUpdateNode(Node n) { n instanceof PostUpdateNode or none() }
query predicate postWithInFlow(Node n, string msg) {
isPostUpdateNode(n) and
not clearsContent(n, _) and
simpleLocalFlowStep(_, n) and
not any(ConsistencyConfiguration c).postWithInFlowExclude(n) and
msg = "PostUpdateNode should not be the target of local flow."
}
query predicate viableImplInCallContextTooLarge(
DataFlowCall call, DataFlowCall ctx, DataFlowCallable callable
) {
callable = viableImplInCallContext(call, ctx) and
not callable = viableCallable(call) and
not any(ConsistencyConfiguration c).viableImplInCallContextTooLargeExclude(call, ctx, callable)
}
}

View File

@@ -1,11 +0,0 @@
/**
* Provides IR-specific definitions for use in the data flow library.
*/
module Private {
import DataFlowPrivate
import DataFlowDispatch
}
module Public {
import DataFlowUtil
}

View File

@@ -1,560 +0,0 @@
private import cpp as Cpp
private import DataFlowUtil
private import semmle.code.cpp.ir.IR
private import DataFlowDispatch
private import DataFlowImplConsistency
private import semmle.code.cpp.ir.internal.IRCppLanguage
private import SsaInternals as Ssa
/** Gets the callable in which this node occurs. */
DataFlowCallable nodeGetEnclosingCallable(Node n) { result = n.getEnclosingCallable() }
/** Holds if `p` is a `ParameterNode` of `c` with position `pos`. */
predicate isParameterNode(ParameterNode p, DataFlowCallable c, ParameterPosition pos) {
p.isParameterOf(c, pos)
}
/** Holds if `arg` is an `ArgumentNode` of `c` with position `pos`. */
predicate isArgumentNode(ArgumentNode arg, DataFlowCall c, ArgumentPosition pos) {
arg.argumentOf(c, pos)
}
/**
* A data flow node that occurs as the argument of a call and is passed as-is
* to the callable. Instance arguments (`this` pointer) and read side effects
* on parameters are also included.
*/
abstract class ArgumentNode extends Node {
/**
* Holds if this argument occurs at the given position in the given call.
* The instance argument is considered to have index `-1`.
*/
abstract predicate argumentOf(DataFlowCall call, ArgumentPosition pos);
/** Gets the call in which this node is an argument. */
DataFlowCall getCall() { this.argumentOf(result, _) }
}
/**
* A data flow node that occurs as the argument to a call, or an
* implicit `this` pointer argument.
*/
private class PrimaryArgumentNode extends ArgumentNode, OperandNode {
override ArgumentOperand op;
PrimaryArgumentNode() { exists(CallInstruction call | op = call.getAnArgumentOperand()) }
override predicate argumentOf(DataFlowCall call, ArgumentPosition pos) {
op = call.getArgumentOperand(pos.(DirectPosition).getIndex())
}
override string toStringImpl() { result = argumentOperandToString(op) }
}
private string argumentOperandToString(ArgumentOperand op) {
exists(Expr unconverted |
unconverted = op.getDef().getUnconvertedResultExpression() and
result = unconverted.toString()
)
or
// Certain instructions don't map to an unconverted result expression. For these cases
// we fall back to a simpler naming scheme. This can happen in IR-generated constructors.
not exists(op.getDef().getUnconvertedResultExpression()) and
(
result = "Argument " + op.(PositionalArgumentOperand).getIndex()
or
op instanceof ThisArgumentOperand and result = "Argument this"
)
}
private class SideEffectArgumentNode extends ArgumentNode, SideEffectOperandNode {
override predicate argumentOf(DataFlowCall dfCall, ArgumentPosition pos) {
this.getCallInstruction() = dfCall and
pos.(IndirectionPosition).getArgumentIndex() = this.getArgumentIndex() and
pos.(IndirectionPosition).getIndirectionIndex() = super.getIndirectionIndex()
}
override string toStringImpl() {
result = argumentOperandToString(this.getAddressOperand()) + " indirection"
}
}
/** A parameter position represented by an integer. */
class ParameterPosition = Position;
/** An argument position represented by an integer. */
class ArgumentPosition = Position;
class Position extends TPosition {
abstract string toString();
}
class DirectPosition extends Position, TDirectPosition {
int index;
DirectPosition() { this = TDirectPosition(index) }
override string toString() { if index = -1 then result = "this" else result = index.toString() }
int getIndex() { result = index }
}
class IndirectionPosition extends Position, TIndirectionPosition {
int argumentIndex;
int indirectionIndex;
IndirectionPosition() { this = TIndirectionPosition(argumentIndex, indirectionIndex) }
override string toString() {
if argumentIndex = -1
then if indirectionIndex > 0 then result = "this indirection" else result = "this"
else
if indirectionIndex > 0
then result = argumentIndex.toString() + " indirection"
else result = argumentIndex.toString()
}
int getArgumentIndex() { result = argumentIndex }
int getIndirectionIndex() { result = indirectionIndex }
}
newtype TPosition =
TDirectPosition(int index) { exists(any(CallInstruction c).getArgument(index)) } or
TIndirectionPosition(int argumentIndex, int indirectionIndex) {
hasOperandAndIndex(_, any(CallInstruction call).getArgumentOperand(argumentIndex),
indirectionIndex)
}
private newtype TReturnKind =
TNormalReturnKind(int index) {
exists(IndirectReturnNode return |
return.getAddressOperand() = any(ReturnValueInstruction r).getReturnAddressOperand() and
index = return.getIndirectionIndex() - 1 // We subtract one because the return loads the value.
)
} or
TIndirectReturnKind(int argumentIndex, int indirectionIndex) {
exists(IndirectReturnNode return, ReturnIndirectionInstruction returnInd |
returnInd.hasIndex(argumentIndex) and
return.getAddressOperand() = returnInd.getSourceAddressOperand() and
indirectionIndex = return.getIndirectionIndex()
)
}
/**
* A return kind. A return kind describes how a value can be returned
* from a callable. For C++, this is simply a function return.
*/
class ReturnKind extends TReturnKind {
/** Gets a textual representation of this return kind. */
abstract string toString();
}
private class NormalReturnKind extends ReturnKind, TNormalReturnKind {
int index;
NormalReturnKind() { this = TNormalReturnKind(index) }
override string toString() { result = "indirect return" }
}
private class IndirectReturnKind extends ReturnKind, TIndirectReturnKind {
int argumentIndex;
int indirectionIndex;
IndirectReturnKind() { this = TIndirectReturnKind(argumentIndex, indirectionIndex) }
override string toString() { result = "indirect outparam[" + argumentIndex.toString() + "]" }
}
/** A data flow node that occurs as the result of a `ReturnStmt`. */
class ReturnNode extends Node instanceof IndirectReturnNode {
/** Gets the kind of this returned value. */
abstract ReturnKind getKind();
}
/**
* This predicate represents an annoying hack that we have to do. We use the
* `ReturnIndirectionInstruction` to determine which variables need flow back
* out of a function. However, the IR will unconditionally create those for a
* variable passed to a function even though the variable was never updated by
* the function. And if a function has too many `ReturnNode`s the dataflow
* library lowers its precision for that function by disabling field flow.
*
* So we those eliminate `ReturnNode`s that would have otherwise been created
* by this unconditional `ReturnIndirectionInstruction` by requiring that there
* must exist an SSA definition of the IR variable in the function.
*/
private predicate hasNonInitializeParameterDef(IRVariable v) {
exists(Ssa::Def def |
not def.getDefiningInstruction() instanceof InitializeParameterInstruction and
v = def.getSourceVariable().getBaseVariable().(Ssa::BaseIRVariable).getIRVariable()
)
}
class ReturnIndirectionNode extends IndirectReturnNode, ReturnNode {
override ReturnKind getKind() {
exists(int argumentIndex, ReturnIndirectionInstruction returnInd |
returnInd.hasIndex(argumentIndex) and
this.getAddressOperand() = returnInd.getSourceAddressOperand() and
result = TIndirectReturnKind(argumentIndex, this.getIndirectionIndex()) and
hasNonInitializeParameterDef(returnInd.getIRVariable())
)
or
this.getAddressOperand() = any(ReturnValueInstruction r).getReturnAddressOperand() and
result = TNormalReturnKind(this.getIndirectionIndex() - 1)
}
}
private Operand fullyConvertedCallStep(Operand op) {
not exists(getANonConversionUse(op)) and
exists(Instruction instr |
conversionFlow(op, instr, _) and
result = getAUse(instr)
)
}
/**
* Gets the instruction that uses this operand, if the instruction is not
* ignored for dataflow purposes.
*/
private Instruction getUse(Operand op) {
result = op.getUse() and
not Ssa::ignoreOperand(op)
}
/** Gets a use of the instruction `instr` that is not ignored for dataflow purposes. */
Operand getAUse(Instruction instr) {
result = instr.getAUse() and
not Ssa::ignoreOperand(result)
}
/**
* Gets a use of `operand` that is:
* - not ignored for dataflow purposes, and
* - not a conversion-like instruction.
*/
private Instruction getANonConversionUse(Operand operand) {
result = getUse(operand) and
not conversionFlow(_, result, _)
}
/**
* Gets the operand that represents the first use of the value of `call` following
* a sequence of conversion-like instructions.
*/
predicate operandForfullyConvertedCall(Operand operand, CallInstruction call) {
exists(getANonConversionUse(operand)) and
(
operand = getAUse(call)
or
operand = fullyConvertedCallStep*(getAUse(call))
)
}
/**
* Gets the instruction that represents the first use of the value of `call` following
* a sequence of conversion-like instructions.
*
* This predicate only holds if there is no suitable operand (i.e., no operand of a non-
* conversion instruction) to use to represent the value of `call` after conversions.
*/
predicate instructionForfullyConvertedCall(Instruction instr, CallInstruction call) {
not operandForfullyConvertedCall(_, call) and
(
// If there is no use of the call then we pick the call instruction
not exists(getAUse(call)) and
instr = call
or
// Otherwise, flow to the first non-conversion use.
exists(Operand operand | operand = fullyConvertedCallStep*(getAUse(call)) |
instr = getANonConversionUse(operand)
)
)
}
/** Holds if `node` represents the output node for `call`. */
private predicate simpleOutNode(Node node, CallInstruction call) {
operandForfullyConvertedCall(node.asOperand(), call)
or
instructionForfullyConvertedCall(node.asInstruction(), call)
}
/** A data flow node that represents the output of a call. */
class OutNode extends Node {
OutNode() {
// Return values not hidden behind indirections
simpleOutNode(this, _)
or
// Return values hidden behind indirections
this instanceof IndirectReturnOutNode
or
// Modified arguments hidden behind indirections
this instanceof IndirectArgumentOutNode
}
/** Gets the underlying call. */
abstract DataFlowCall getCall();
abstract ReturnKind getReturnKind();
}
private class DirectCallOutNode extends OutNode {
CallInstruction call;
DirectCallOutNode() { simpleOutNode(this, call) }
override DataFlowCall getCall() { result = call }
override ReturnKind getReturnKind() { result = TNormalReturnKind(0) }
}
private class IndirectCallOutNode extends OutNode, IndirectReturnOutNode {
override DataFlowCall getCall() { result = this.getCallInstruction() }
override ReturnKind getReturnKind() { result = TNormalReturnKind(this.getIndirectionIndex()) }
}
private class SideEffectOutNode extends OutNode, IndirectArgumentOutNode {
override DataFlowCall getCall() { result = this.getCallInstruction() }
override ReturnKind getReturnKind() {
result = TIndirectReturnKind(this.getArgumentIndex(), this.getIndirectionIndex())
}
}
/**
* Gets a node that can read the value returned from `call` with return kind
* `kind`.
*/
OutNode getAnOutNode(DataFlowCall call, ReturnKind kind) {
result.getCall() = call and
result.getReturnKind() = kind
}
/**
* Holds if data can flow from `node1` to `node2` in a way that loses the
* calling context. For example, this would happen with flow through a
* global or static variable.
*/
predicate jumpStep(Node n1, Node n2) {
exists(Cpp::GlobalOrNamespaceVariable v |
v =
n1.asInstruction()
.(StoreInstruction)
.getResultAddress()
.(VariableAddressInstruction)
.getAstVariable() and
v = n2.asVariable()
or
v =
n2.asInstruction()
.(LoadInstruction)
.getSourceAddress()
.(VariableAddressInstruction)
.getAstVariable() and
v = n1.asVariable()
)
}
/**
* Holds if data can flow from `node1` to `node2` via an assignment to `f`.
* Thus, `node2` references an object with a field `f` that contains the
* value of `node1`.
*/
predicate storeStep(Node node1, Content c, PostFieldUpdateNode node2) {
exists(int indirectionIndex1, int numberOfLoads, StoreInstruction store |
nodeHasInstruction(node1, store, pragma[only_bind_into](indirectionIndex1)) and
node2.getIndirectionIndex() = 1 and
numberOfLoadsFromOperand(node2.getFieldAddress(), store.getDestinationAddressOperand(),
numberOfLoads)
|
exists(FieldContent fc | fc = c |
fc.getField() = node2.getUpdatedField() and
fc.getIndirectionIndex() = 1 + indirectionIndex1 + numberOfLoads
)
or
exists(UnionContent uc | uc = c |
uc.getAField() = node2.getUpdatedField() and
uc.getIndirectionIndex() = 1 + indirectionIndex1 + numberOfLoads
)
)
}
/**
* Holds if `operandFrom` flows to `operandTo` using a sequence of conversion-like
* operations and exactly `n` `LoadInstruction` operations.
*/
private predicate numberOfLoadsFromOperandRec(Operand operandFrom, Operand operandTo, int ind) {
exists(LoadInstruction load | load.getSourceAddressOperand() = operandFrom |
operandTo = operandFrom and ind = 0
or
numberOfLoadsFromOperand(load.getAUse(), operandTo, ind - 1)
)
or
exists(Operand op, Instruction instr |
instr = op.getDef() and
conversionFlow(operandFrom, instr, _) and
numberOfLoadsFromOperand(op, operandTo, ind)
)
}
/**
* Holds if `operandFrom` flows to `operandTo` using a sequence of conversion-like
* operations and exactly `n` `LoadInstruction` operations.
*/
private predicate numberOfLoadsFromOperand(Operand operandFrom, Operand operandTo, int n) {
numberOfLoadsFromOperandRec(operandFrom, operandTo, n)
or
not any(LoadInstruction load).getSourceAddressOperand() = operandFrom and
not conversionFlow(operandFrom, _, _) and
operandFrom = operandTo and
n = 0
}
// Needed to join on both an operand and an index at the same time.
pragma[noinline]
predicate nodeHasOperand(Node node, Operand operand, int indirectionIndex) {
node.asOperand() = operand and indirectionIndex = 0
or
hasOperandAndIndex(node, operand, indirectionIndex)
}
// Needed to join on both an instruction and an index at the same time.
pragma[noinline]
predicate nodeHasInstruction(Node node, Instruction instr, int indirectionIndex) {
node.asInstruction() = instr and indirectionIndex = 0
or
hasInstructionAndIndex(node, instr, indirectionIndex)
}
/**
* Holds if data can flow from `node1` to `node2` via a read of `f`.
* Thus, `node1` references an object with a field `f` whose value ends up in
* `node2`.
*/
predicate readStep(Node node1, Content c, Node node2) {
exists(FieldAddress fa1, Operand operand, int numberOfLoads, int indirectionIndex2 |
nodeHasOperand(node2, operand, indirectionIndex2) and
nodeHasOperand(node1, fa1.getObjectAddressOperand(), _) and
numberOfLoadsFromOperand(fa1, operand, numberOfLoads)
|
exists(FieldContent fc | fc = c |
fc.getField() = fa1.getField() and
fc.getIndirectionIndex() = indirectionIndex2 + numberOfLoads
)
or
exists(UnionContent uc | uc = c |
uc.getAField() = fa1.getField() and
uc.getIndirectionIndex() = indirectionIndex2 + numberOfLoads
)
)
}
/**
* Holds if values stored inside content `c` are cleared at node `n`.
*/
predicate clearsContent(Node n, Content c) {
none() // stub implementation
}
/**
* Holds if the value that is being tracked is expected to be stored inside content `c`
* at node `n`.
*/
predicate expectsContent(Node n, ContentSet c) { none() }
/** Gets the type of `n` used for type pruning. */
DataFlowType getNodeType(Node n) {
suppressUnusedNode(n) and
result instanceof VoidType // stub implementation
}
/** Gets a string representation of a type returned by `getNodeType`. */
string ppReprType(DataFlowType t) { none() } // stub implementation
/**
* Holds if `t1` and `t2` are compatible, that is, whether data can flow from
* a node of type `t1` to a node of type `t2`.
*/
pragma[inline]
predicate compatibleTypes(DataFlowType t1, DataFlowType t2) {
any() // stub implementation
}
private predicate suppressUnusedNode(Node n) { any() }
//////////////////////////////////////////////////////////////////////////////
// Java QL library compatibility wrappers
//////////////////////////////////////////////////////////////////////////////
/** A node that performs a type cast. */
class CastNode extends Node {
CastNode() { none() } // stub implementation
}
/**
* A function that may contain code or a variable that may contain itself. When
* flow crosses from one _enclosing callable_ to another, the interprocedural
* data-flow library discards call contexts and inserts a node in the big-step
* relation used for human-readable path explanations.
*/
class DataFlowCallable = Cpp::Declaration;
class DataFlowExpr = Expr;
class DataFlowType = Type;
/** A function call relevant for data flow. */
class DataFlowCall extends CallInstruction {
Function getEnclosingCallable() { result = this.getEnclosingFunction() }
}
predicate isUnreachableInCall(Node n, DataFlowCall call) { none() } // stub implementation
int accessPathLimit() { result = 5 }
/**
* Holds if access paths with `c` at their head always should be tracked at high
* precision. This disables adaptive access path precision for such access paths.
*/
predicate forceHighPrecision(Content c) { none() }
/** The unit type. */
private newtype TUnit = TMkUnit()
/** The trivial type with a single element. */
class Unit extends TUnit {
/** Gets a textual representation of this element. */
string toString() { result = "unit" }
}
/** Holds if `n` should be hidden from path explanations. */
predicate nodeIsHidden(Node n) { n instanceof OperandNode and not n instanceof ArgumentNode }
class LambdaCallKind = Unit;
/** Holds if `creation` is an expression that creates a lambda of kind `kind` for `c`. */
predicate lambdaCreation(Node creation, LambdaCallKind kind, DataFlowCallable c) { none() }
/** Holds if `call` is a lambda call of kind `kind` where `receiver` is the lambda expression. */
predicate lambdaCall(DataFlowCall call, LambdaCallKind kind, Node receiver) { none() }
/** Extra data-flow steps needed for lambda flow analysis. */
predicate additionalLambdaFlowStep(Node nodeFrom, Node nodeTo, boolean preservesValue) { none() }
/**
* Holds if flow is allowed to pass from parameter `p` and back to itself as a
* side-effect, resulting in a summary from `p` to itself.
*
* One example would be to allow flow like `p.foo = p.bar;`, which is disallowed
* by default as a heuristic.
*/
predicate allowParameterReturnInSelf(ParameterNode p) { none() }
private class MyConsistencyConfiguration extends Consistency::ConsistencyConfiguration {
override predicate argHasPostUpdateExclude(ArgumentNode n) {
// The rules for whether an IR argument gets a post-update node are too
// complex to model here.
any()
}
}

View File

@@ -1,93 +0,0 @@
/**
* Provides predicates for mapping the `FunctionInput` and `FunctionOutput`
* classes used in function models to the corresponding instructions.
*/
private import semmle.code.cpp.ir.IR
private import experimental.semmle.code.cpp.ir.dataflow.DataFlow
private import experimental.semmle.code.cpp.ir.dataflow.internal.DataFlowUtil
private import SsaInternals as Ssa
/**
* Gets the instruction that goes into `input` for `call`.
*/
DataFlow::Node callInput(CallInstruction call, FunctionInput input) {
// An argument or qualifier
exists(int index |
result.asOperand() = call.getArgumentOperand(index) and
input.isParameterOrQualifierAddress(index)
)
or
// A value pointed to by an argument or qualifier
exists(int index, int indirectionIndex |
hasOperandAndIndex(result, call.getArgumentOperand(index), indirectionIndex) and
input.isParameterDerefOrQualifierObject(index, indirectionIndex)
)
or
exists(int ind |
result = getIndirectReturnOutNode(call, ind) and
input.isReturnValueDeref(ind)
)
}
/**
* Gets the instruction that holds the `output` for `call`.
*/
Node callOutput(CallInstruction call, FunctionOutput output) {
// The return value
result.asInstruction() = call and
output.isReturnValue()
or
// The side effect of a call on the value pointed to by an argument or qualifier
exists(int index, int indirectionIndex |
result.(IndirectArgumentOutNode).getArgumentIndex() = index and
result.(IndirectArgumentOutNode).getIndirectionIndex() = indirectionIndex and
result.(IndirectArgumentOutNode).getCallInstruction() = call and
output.isParameterDerefOrQualifierObject(index, indirectionIndex)
)
or
exists(int ind |
result = getIndirectReturnOutNode(call, ind) and
output.isReturnValueDeref(ind)
)
}
DataFlow::Node callInput(CallInstruction call, FunctionInput input, int d) {
exists(DataFlow::Node n | n = callInput(call, input) and d > 0 |
// An argument or qualifier
hasOperandAndIndex(result, n.asOperand(), d)
or
exists(Operand operand, int indirectionIndex |
// A value pointed to by an argument or qualifier
hasOperandAndIndex(n, operand, indirectionIndex) and
hasOperandAndIndex(result, operand, indirectionIndex + d)
)
)
}
private IndirectReturnOutNode getIndirectReturnOutNode(CallInstruction call, int d) {
result.getCallInstruction() = call and
result.getIndirectionIndex() = d
}
/**
* Gets the instruction that holds the `output` for `call`.
*/
bindingset[d]
Node callOutput(CallInstruction call, FunctionOutput output, int d) {
exists(DataFlow::Node n | n = callOutput(call, output) and d > 0 |
// The return value
result = getIndirectReturnOutNode(n.asInstruction(), d)
or
// If there isn't an indirect out node for the call with indirection `d` then
// we conflate this with the underlying `CallInstruction`.
not exists(getIndirectReturnOutNode(call, d)) and
n.asInstruction() = result.asInstruction()
or
// The side effect of a call on the value pointed to by an argument or qualifier
exists(Operand operand, int indirectionIndex |
Ssa::outNodeHasAddressAndIndex(n, operand, indirectionIndex) and
Ssa::outNodeHasAddressAndIndex(result, operand, indirectionIndex + d)
)
)
}

View File

@@ -1,136 +0,0 @@
private import cpp
// The `ValueNumbering` library has to be imported right after `cpp` to ensure
// that the cached IR gets the same checksum here as it does in queries that use
// `ValueNumbering` without `DataFlow`.
private import semmle.code.cpp.ir.ValueNumbering
private import semmle.code.cpp.ir.IR
private import semmle.code.cpp.ir.dataflow.DataFlow
private import semmle.code.cpp.ir.dataflow.internal.DataFlowUtil
private import PrintIRUtilities
/**
* Gets the local dataflow from other nodes in the same function to this node.
*/
private string getFromFlow(DataFlow::Node useNode, int order1, int order2) {
exists(DataFlow::Node defNode, string prefix |
(
simpleLocalFlowStep(defNode, useNode) and prefix = ""
or
any(DataFlow::Configuration cfg).isAdditionalFlowStep(defNode, useNode) and
defNode.getEnclosingCallable() = useNode.getEnclosingCallable() and
prefix = "+"
) and
if defNode.asInstruction() = useNode.asOperand().getAnyDef()
then
// Shorthand for flow from the def of this operand.
result = prefix + "def" and
order1 = -1 and
order2 = 0
else
if defNode.asOperand().getUse() = useNode.asInstruction()
then
// Shorthand for flow from an operand of this instruction
result = prefix + defNode.asOperand().getDumpId() and
order1 = -1 and
order2 = defNode.asOperand().getDumpSortOrder()
else result = prefix + nodeId(defNode, order1, order2)
)
}
/**
* Gets the local dataflow from this node to other nodes in the same function.
*/
private string getToFlow(DataFlow::Node defNode, int order1, int order2) {
exists(DataFlow::Node useNode, string prefix |
(
simpleLocalFlowStep(defNode, useNode) and prefix = ""
or
any(DataFlow::Configuration cfg).isAdditionalFlowStep(defNode, useNode) and
defNode.getEnclosingCallable() = useNode.getEnclosingCallable() and
prefix = "+"
) and
if useNode.asInstruction() = defNode.asOperand().getUse()
then
// Shorthand for flow to this operand's instruction.
result = prefix + "result" and
order1 = -1 and
order2 = 0
else result = prefix + nodeId(useNode, order1, order2)
)
}
/**
* Gets the properties of the dataflow node `node`.
*/
private string getNodeProperty(DataFlow::Node node, string key) {
// List dataflow into and out of this node. Flow into this node is printed as `src->@`, and flow
// out of this node is printed as `@->dest`.
key = "flow" and
result =
strictconcat(string flow, boolean to, int order1, int order2 |
flow = getFromFlow(node, order1, order2) + "->@" and to = false
or
flow = "@->" + getToFlow(node, order1, order2) and to = true
|
flow, ", " order by to, order1, order2, flow
)
or
// Is this node a dataflow sink?
key = "sink" and
any(DataFlow::Configuration cfg).isSink(node) and
result = "true"
or
// Is this node a dataflow source?
key = "source" and
any(DataFlow::Configuration cfg).isSource(node) and
result = "true"
or
// Is this node a dataflow barrier, and if so, what kind?
key = "barrier" and
result =
strictconcat(string kind |
any(DataFlow::Configuration cfg).isBarrier(node) and kind = "full"
or
any(DataFlow::Configuration cfg).isBarrierIn(node) and kind = "in"
or
any(DataFlow::Configuration cfg).isBarrierOut(node) and kind = "out"
|
kind, ", "
)
or
// Is there partial flow from a source to this node?
// This property will only be emitted if partial flow is enabled by overriding
// `DataFlow::Configuration::explorationLimit()`.
key = "pflow" and
result =
strictconcat(DataFlow::PartialPathNode sourceNode, DataFlow::PartialPathNode destNode, int dist,
int order1, int order2 |
any(DataFlow::Configuration cfg).hasPartialFlow(sourceNode, destNode, dist) and
destNode.getNode() = node and
// Only print flow from a source in the same function.
sourceNode.getNode().getEnclosingCallable() = node.getEnclosingCallable()
|
nodeId(sourceNode.getNode(), order1, order2) + "+" + dist.toString(), ", "
order by
order1, order2, dist desc
)
}
/**
* Property provider for local IR dataflow.
*/
class LocalFlowPropertyProvider extends IRPropertyProvider {
override string getOperandProperty(Operand operand, string key) {
exists(DataFlow::Node node |
operand = node.asOperand() and
result = getNodeProperty(node, key)
)
}
override string getInstructionProperty(Instruction instruction, string key) {
exists(DataFlow::Node node |
instruction = node.asInstruction() and
result = getNodeProperty(node, key)
)
}
}

View File

@@ -1,33 +0,0 @@
/**
* Print the dataflow local store steps in IR dumps.
*/
private import cpp
// The `ValueNumbering` library has to be imported right after `cpp` to ensure
// that the cached IR gets the same checksum here as it does in queries that use
// `ValueNumbering` without `DataFlow`.
private import semmle.code.cpp.ir.ValueNumbering
private import semmle.code.cpp.ir.IR
private import semmle.code.cpp.ir.dataflow.DataFlow
private import semmle.code.cpp.ir.dataflow.internal.DataFlowUtil
private import semmle.code.cpp.ir.dataflow.internal.DataFlowPrivate
private import PrintIRUtilities
/**
* Property provider for local IR dataflow store steps.
*/
class LocalFlowPropertyProvider extends IRPropertyProvider {
override string getInstructionProperty(Instruction instruction, string key) {
exists(DataFlow::Node objectNode, Content content |
key = "content[" + content.toString() + "]" and
instruction = objectNode.asInstruction() and
result =
strictconcat(string element, DataFlow::Node fieldNode |
storeStep(fieldNode, content, objectNode) and
element = nodeId(fieldNode, _, _)
|
element, ", "
)
)
}
}

View File

@@ -1,39 +0,0 @@
/**
* Shared utilities used when printing dataflow annotations in IR dumps.
*/
private import cpp
// The `ValueNumbering` library has to be imported right after `cpp` to ensure
// that the cached IR gets the same checksum here as it does in queries that use
// `ValueNumbering` without `DataFlow`.
private import semmle.code.cpp.ir.ValueNumbering
private import semmle.code.cpp.ir.IR
private import semmle.code.cpp.ir.dataflow.DataFlow
/**
* Gets a short ID for an IR dataflow node.
* - For `Instruction`s, this is just the result ID of the instruction (e.g. `m128`).
* - For `Operand`s, this is the label of the operand, prefixed with the result ID of the
* instruction and a dot (e.g. `m128.left`).
* - For `Variable`s, this is the qualified name of the variable.
*/
string nodeId(DataFlow::Node node, int order1, int order2) {
exists(Instruction instruction | instruction = node.asInstruction() |
result = instruction.getResultId() and
order1 = instruction.getBlock().getDisplayIndex() and
order2 = instruction.getDisplayIndexInBlock()
)
or
exists(Operand operand, Instruction instruction |
operand = node.asOperand() and
instruction = operand.getUse()
|
result = instruction.getResultId() + "." + operand.getDumpId() and
order1 = instruction.getBlock().getDisplayIndex() and
order2 = instruction.getDisplayIndexInBlock()
)
or
result = "var(" + node.asVariable().getQualifiedName() + ")" and
order1 = 1000000 and
order2 = 0
}

View File

@@ -1,552 +0,0 @@
private import codeql.ssa.Ssa as SsaImplCommon
private import semmle.code.cpp.ir.IR
private import DataFlowUtil
private import DataFlowImplCommon as DataFlowImplCommon
private import semmle.code.cpp.models.interfaces.Allocation as Alloc
private import semmle.code.cpp.models.interfaces.DataFlow as DataFlow
private import semmle.code.cpp.ir.internal.IRCppLanguage
private import DataFlowPrivate
private import ssa0.SsaInternals as SsaInternals0
import SsaInternalsCommon
private module SourceVariables {
int getMaxIndirectionForIRVariable(IRVariable var) {
exists(Type type, boolean isGLValue |
var.getLanguageType().hasType(type, isGLValue) and
if isGLValue = true
then result = 1 + getMaxIndirectionsForType(type)
else result = getMaxIndirectionsForType(type)
)
}
class BaseSourceVariable = SsaInternals0::BaseSourceVariable;
class BaseIRVariable = SsaInternals0::BaseIRVariable;
class BaseCallVariable = SsaInternals0::BaseCallVariable;
cached
private newtype TSourceVariable =
TSourceIRVariable(BaseIRVariable baseVar, int ind) {
ind = [0 .. getMaxIndirectionForIRVariable(baseVar.getIRVariable())]
} or
TCallVariable(AllocationInstruction call, int ind) {
ind = [0 .. countIndirectionsForCppType(getResultLanguageType(call))]
}
abstract class SourceVariable extends TSourceVariable {
int ind;
bindingset[ind]
SourceVariable() { any() }
abstract string toString();
int getIndirection() { result = ind }
abstract BaseSourceVariable getBaseVariable();
}
class SourceIRVariable extends SourceVariable, TSourceIRVariable {
BaseIRVariable var;
SourceIRVariable() { this = TSourceIRVariable(var, ind) }
IRVariable getIRVariable() { result = var.getIRVariable() }
override BaseIRVariable getBaseVariable() { result.getIRVariable() = this.getIRVariable() }
override string toString() {
ind = 0 and
result = this.getIRVariable().toString()
or
ind > 0 and
result = this.getIRVariable().toString() + " indirection"
}
}
class CallVariable extends SourceVariable, TCallVariable {
AllocationInstruction call;
CallVariable() { this = TCallVariable(call, ind) }
AllocationInstruction getCall() { result = call }
override BaseCallVariable getBaseVariable() { result.getCallInstruction() = call }
override string toString() {
ind = 0 and
result = "Call"
or
ind > 0 and
result = "Call indirection"
}
}
}
import SourceVariables
predicate hasIndirectOperand(Operand op, int indirectionIndex) {
exists(CppType type, int m |
not ignoreOperand(op) and
type = getLanguageType(op) and
m = countIndirectionsForCppType(type) and
indirectionIndex = [1 .. m]
)
}
predicate hasIndirectInstruction(Instruction instr, int indirectionIndex) {
exists(CppType type, int m |
not ignoreInstruction(instr) and
type = getResultLanguageType(instr) and
m = countIndirectionsForCppType(type) and
indirectionIndex = [1 .. m]
)
}
cached
private newtype TDefOrUseImpl =
TDefImpl(Operand address, int indirectionIndex) {
isDef(_, _, address, _, _, indirectionIndex) and
// We only include the definition if the SSA pruning stage
// concluded that the definition is live after the write.
any(SsaInternals0::Def def).getAddressOperand() = address
} or
TUseImpl(Operand operand, int indirectionIndex) {
isUse(_, operand, _, _, indirectionIndex) and
not isDef(_, _, operand, _, _, _)
}
abstract private class DefOrUseImpl extends TDefOrUseImpl {
/** Gets a textual representation of this element. */
abstract string toString();
/** Gets the block of this definition or use. */
abstract IRBlock getBlock();
/** Holds if this definition or use has index `index` in block `block`. */
abstract predicate hasIndexInBlock(IRBlock block, int index);
final predicate hasIndexInBlock(IRBlock block, int index, SourceVariable sv) {
this.hasIndexInBlock(block, index) and
sv = this.getSourceVariable()
}
/** Gets the location of this element. */
abstract Cpp::Location getLocation();
/**
* Gets the index (i.e., the number of loads required) of this
* definition or use.
*
* Note that this is _not_ the definition's (or use's) index in
* the enclosing basic block. To obtain this index, use
* `DefOrUseImpl::hasIndexInBlock/2` or `DefOrUseImpl::hasIndexInBlock/3`.
*/
abstract int getIndirectionIndex();
/**
* Gets the instruction that computes the base of this definition or use.
* This is always a `VariableAddressInstruction` or an `AllocationInstruction`.
*/
abstract Instruction getBase();
final BaseSourceVariable getBaseSourceVariable() {
exists(IRVariable var |
result.(BaseIRVariable).getIRVariable() = var and
instructionHasIRVariable(this.getBase(), var)
)
or
result.(BaseCallVariable).getCallInstruction() = this.getBase()
}
/** Gets the variable that is defined or used. */
final SourceVariable getSourceVariable() {
exists(BaseSourceVariable v, int ind |
sourceVariableHasBaseAndIndex(result, v, ind) and
defOrUseHasSourceVariable(this, v, ind)
)
}
}
pragma[noinline]
private predicate instructionHasIRVariable(VariableAddressInstruction vai, IRVariable var) {
vai.getIRVariable() = var
}
private predicate defOrUseHasSourceVariable(DefOrUseImpl defOrUse, BaseSourceVariable bv, int ind) {
defHasSourceVariable(defOrUse, bv, ind)
or
useHasSourceVariable(defOrUse, bv, ind)
}
pragma[noinline]
private predicate defHasSourceVariable(DefImpl def, BaseSourceVariable bv, int ind) {
bv = def.getBaseSourceVariable() and
ind = def.getIndirection()
}
pragma[noinline]
private predicate useHasSourceVariable(UseImpl use, BaseSourceVariable bv, int ind) {
bv = use.getBaseSourceVariable() and
ind = use.getIndirection()
}
pragma[noinline]
private predicate sourceVariableHasBaseAndIndex(SourceVariable v, BaseSourceVariable bv, int ind) {
v.getBaseVariable() = bv and
v.getIndirection() = ind
}
class DefImpl extends DefOrUseImpl, TDefImpl {
Operand address;
int ind;
DefImpl() { this = TDefImpl(address, ind) }
override Instruction getBase() { isDef(_, _, address, result, _, _) }
Operand getAddressOperand() { result = address }
int getIndirection() { isDef(_, _, address, _, result, ind) }
override int getIndirectionIndex() { result = ind }
Instruction getDefiningInstruction() { isDef(_, result, address, _, _, _) }
override string toString() { result = "DefImpl" }
override IRBlock getBlock() { result = this.getDefiningInstruction().getBlock() }
override Cpp::Location getLocation() { result = this.getDefiningInstruction().getLocation() }
final override predicate hasIndexInBlock(IRBlock block, int index) {
this.getDefiningInstruction() = block.getInstruction(index)
}
predicate isCertain() { isDef(true, _, address, _, _, ind) }
}
class UseImpl extends DefOrUseImpl, TUseImpl {
Operand operand;
int ind;
UseImpl() { this = TUseImpl(operand, ind) }
Operand getOperand() { result = operand }
override string toString() { result = "UseImpl" }
final override predicate hasIndexInBlock(IRBlock block, int index) {
operand.getUse() = block.getInstruction(index)
}
final override IRBlock getBlock() { result = operand.getUse().getBlock() }
final override Cpp::Location getLocation() { result = operand.getLocation() }
final int getIndirection() { isUse(_, operand, _, result, ind) }
override int getIndirectionIndex() { result = ind }
override Instruction getBase() { isUse(_, operand, result, _, ind) }
predicate isCertain() { isUse(true, operand, _, _, ind) }
}
/**
* Holds if `defOrUse1` is a definition which is first read by `use`,
* or if `defOrUse1` is a use and `use` is a next subsequent use.
*
* In both cases, `use` can either be an explicit use written in the
* source file, or it can be a phi node as computed by the SSA library.
*/
predicate adjacentDefRead(DefOrUse defOrUse1, UseOrPhi use) {
exists(IRBlock bb1, int i1, SourceVariable v |
defOrUse1.asDefOrUse().hasIndexInBlock(bb1, i1, v)
|
exists(IRBlock bb2, int i2 |
adjacentDefRead(_, pragma[only_bind_into](bb1), pragma[only_bind_into](i1),
pragma[only_bind_into](bb2), pragma[only_bind_into](i2))
|
use.asDefOrUse().(UseImpl).hasIndexInBlock(bb2, i2, v)
)
or
exists(PhiNode phi |
lastRefRedef(_, bb1, i1, phi) and
use.asPhi() = phi and
phi.getSourceVariable() = pragma[only_bind_into](v)
)
)
}
private predicate useToNode(UseOrPhi use, Node nodeTo) {
exists(UseImpl useImpl |
useImpl = use.asDefOrUse() and
nodeHasOperand(nodeTo, useImpl.getOperand(), useImpl.getIndirectionIndex())
)
or
nodeTo.(SsaPhiNode).getPhiNode() = use.asPhi()
}
pragma[noinline]
predicate outNodeHasAddressAndIndex(
IndirectArgumentOutNode out, Operand address, int indirectionIndex
) {
out.getAddressOperand() = address and
out.getIndirectionIndex() = indirectionIndex
}
private predicate defToNode(Node nodeFrom, Def def) {
nodeHasInstruction(nodeFrom, def.getDefiningInstruction(), def.getIndirectionIndex())
}
/**
* INTERNAL: Do not use.
*
* Holds if `nodeFrom` is the node that correspond to the definition or use `defOrUse`.
*/
predicate nodeToDefOrUse(Node nodeFrom, SsaDefOrUse defOrUse) {
// Node -> Def
defToNode(nodeFrom, defOrUse)
or
// Node -> Use
useToNode(defOrUse, nodeFrom)
}
/**
* Perform a single conversion-like step from `nFrom` to `nTo`. This relation
* only holds when there is no use-use relation out of `nTo`.
*/
private predicate indirectConversionFlowStep(Node nFrom, Node nTo) {
not exists(UseOrPhi defOrUse |
nodeToDefOrUse(nTo, defOrUse) and
adjacentDefRead(defOrUse, _)
) and
exists(Operand op1, Operand op2, int indirectionIndex, Instruction instr |
hasOperandAndIndex(nFrom, op1, pragma[only_bind_into](indirectionIndex)) and
hasOperandAndIndex(nTo, op2, pragma[only_bind_into](indirectionIndex)) and
instr = op2.getDef() and
conversionFlow(op1, instr, _)
)
}
/**
* The reason for this predicate is a bit annoying:
* We cannot mark a `PointerArithmeticInstruction` that computes an offset based on some SSA
* variable `x` as a use of `x` since this creates taint-flow in the following example:
* ```c
* int x = array[source]
* sink(*array)
* ```
* This is because `source` would flow from the operand of `PointerArithmeticInstruction` to the
* result of the instruction, and into the `IndirectOperand` that represents the value of `*array`.
* Then, via use-use flow, flow will arrive at `*array` in `sink(*array)`.
*
* So this predicate recurses back along conversions and `PointerArithmeticInstruction`s to find the
* first use that has provides use-use flow, and uses that target as the target of the `nodeFrom`.
*/
private predicate adjustForPointerArith(Node nodeFrom, UseOrPhi use) {
nodeFrom = any(PostUpdateNode pun).getPreUpdateNode() and
exists(DefOrUse defOrUse, Node adjusted |
indirectConversionFlowStep*(adjusted, nodeFrom) and
nodeToDefOrUse(adjusted, defOrUse) and
adjacentDefRead(defOrUse, use)
)
}
/** Holds if there is def-use or use-use flow from `nodeFrom` to `nodeTo`. */
predicate ssaFlow(Node nodeFrom, Node nodeTo) {
// `nodeFrom = any(PostUpdateNode pun).getPreUpdateNode()` is implied by adjustedForPointerArith.
exists(UseOrPhi use |
adjustForPointerArith(nodeFrom, use) and
useToNode(use, nodeTo)
)
or
not nodeFrom = any(PostUpdateNode pun).getPreUpdateNode() and
exists(DefOrUse defOrUse1, UseOrPhi use |
nodeToDefOrUse(nodeFrom, defOrUse1) and
adjacentDefRead(defOrUse1, use) and
useToNode(use, nodeTo)
)
}
/** Holds if `nodeTo` receives flow from the phi node `nodeFrom`. */
predicate fromPhiNode(SsaPhiNode nodeFrom, Node nodeTo) {
exists(PhiNode phi, SourceVariable sv, IRBlock bb1, int i1, UseOrPhi use |
phi = nodeFrom.getPhiNode() and
phi.definesAt(sv, bb1, i1) and
useToNode(use, nodeTo)
|
exists(IRBlock bb2, int i2 |
use.asDefOrUse().hasIndexInBlock(bb2, i2, sv) and
adjacentDefRead(phi, bb1, i1, bb2, i2)
)
or
exists(PhiNode phiTo |
lastRefRedef(phi, _, _, phiTo) and
nodeTo.(SsaPhiNode).getPhiNode() = phiTo
)
)
}
private SsaInternals0::SourceVariable getOldSourceVariable(SourceVariable v) {
v.getBaseVariable().(BaseIRVariable).getIRVariable() =
result.getBaseVariable().(SsaInternals0::BaseIRVariable).getIRVariable()
or
v.getBaseVariable().(BaseCallVariable).getCallInstruction() =
result.getBaseVariable().(SsaInternals0::BaseCallVariable).getCallInstruction()
}
/**
* Holds if there is a write at index `i` in basic block `bb` to variable `v` that's
* subsequently read (as determined by the SSA pruning stage).
*/
private predicate variableWriteCand(IRBlock bb, int i, SourceVariable v) {
exists(SsaInternals0::Def def, SsaInternals0::SourceVariable v0 |
def.asDefOrUse().hasIndexInBlock(bb, i, v0) and
v0 = getOldSourceVariable(v)
)
}
private module SsaInput implements SsaImplCommon::InputSig {
import InputSigCommon
import SourceVariables
/**
* Holds if the `i`'th write in block `bb` writes to the variable `v`.
* `certain` is `true` if the write is guaranteed to overwrite the entire variable.
*/
predicate variableWrite(IRBlock bb, int i, SourceVariable v, boolean certain) {
DataFlowImplCommon::forceCachingInSameStage() and
variableWriteCand(bb, i, v) and
exists(DefImpl def | def.hasIndexInBlock(bb, i, v) |
if def.isCertain() then certain = true else certain = false
)
}
/**
* Holds if the `i`'th read in block `bb` reads to the variable `v`.
* `certain` is `true` if the read is guaranteed. For C++, this is always the case.
*/
predicate variableRead(IRBlock bb, int i, SourceVariable v, boolean certain) {
exists(UseImpl use | use.hasIndexInBlock(bb, i, v) |
if use.isCertain() then certain = true else certain = false
)
}
}
/**
* The final SSA predicates used for dataflow purposes.
*/
cached
module SsaCached {
/**
* Holds if `def` is accessed at index `i1` in basic block `bb1` (either a read
* or a write), `def` is read at index `i2` in basic block `bb2`, and there is a
* path between them without any read of `def`.
*/
cached
predicate adjacentDefRead(Definition def, IRBlock bb1, int i1, IRBlock bb2, int i2) {
SsaImpl::adjacentDefRead(def, bb1, i1, bb2, i2)
}
/**
* Holds if the node at index `i` in `bb` is a last reference to SSA definition
* `def`. The reference is last because it can reach another write `next`,
* without passing through another read or write.
*/
cached
predicate lastRefRedef(Definition def, IRBlock bb, int i, Definition next) {
SsaImpl::lastRefRedef(def, bb, i, next)
}
}
cached
private newtype TSsaDefOrUse =
TDefOrUse(DefOrUseImpl defOrUse) {
defOrUse instanceof UseImpl
or
// Like in the pruning stage, we only include definition that's live after the
// write as the final definitions computed by SSA.
exists(Definition def, SourceVariable sv, IRBlock bb, int i |
def.definesAt(sv, bb, i) and
defOrUse.(DefImpl).hasIndexInBlock(bb, i, sv)
)
} or
TPhi(PhiNode phi)
abstract private class SsaDefOrUse extends TSsaDefOrUse {
string toString() { none() }
DefOrUseImpl asDefOrUse() { none() }
PhiNode asPhi() { none() }
abstract Location getLocation();
}
class DefOrUse extends TDefOrUse, SsaDefOrUse {
DefOrUseImpl defOrUse;
DefOrUse() { this = TDefOrUse(defOrUse) }
final override DefOrUseImpl asDefOrUse() { result = defOrUse }
final override Location getLocation() { result = defOrUse.getLocation() }
final SourceVariable getSourceVariable() { result = defOrUse.getSourceVariable() }
override string toString() { result = defOrUse.toString() }
}
class Phi extends TPhi, SsaDefOrUse {
PhiNode phi;
Phi() { this = TPhi(phi) }
final override PhiNode asPhi() { result = phi }
final override Location getLocation() { result = phi.getBasicBlock().getLocation() }
override string toString() { result = "Phi" }
}
class UseOrPhi extends SsaDefOrUse {
UseOrPhi() {
this.asDefOrUse() instanceof UseImpl
or
this instanceof Phi
}
final override Location getLocation() {
result = this.asDefOrUse().getLocation() or result = this.(Phi).getLocation()
}
}
class Def extends DefOrUse {
override DefImpl defOrUse;
Operand getAddressOperand() { result = defOrUse.getAddressOperand() }
Instruction getAddress() { result = this.getAddressOperand().getDef() }
/**
* This predicate ensures that joins go from `defOrUse` to the result
* instead of the other way around.
*/
pragma[inline]
int getIndirectionIndex() {
pragma[only_bind_into](result) = pragma[only_bind_out](defOrUse).getIndirectionIndex()
}
Instruction getDefiningInstruction() { result = defOrUse.getDefiningInstruction() }
}
private module SsaImpl = SsaImplCommon::Make<SsaInput>;
class PhiNode = SsaImpl::PhiNode;
class Definition = SsaImpl::Definition;
import SsaCached

View File

@@ -1,270 +0,0 @@
import cpp as Cpp
import semmle.code.cpp.ir.IR
import semmle.code.cpp.ir.internal.IRCppLanguage
private import semmle.code.cpp.ir.implementation.raw.internal.SideEffects as SideEffects
private import DataFlowImplCommon as DataFlowImplCommon
private import DataFlowUtil
/**
* Holds if `operand` is an operand that is not used by the dataflow library.
* Ignored operands are not recognizd as uses by SSA, and they don't have a
* corresponding `(Indirect)OperandNode`.
*/
predicate ignoreOperand(Operand operand) {
operand = any(Instruction instr | ignoreInstruction(instr)).getAnOperand() or
operand = any(Instruction instr | ignoreInstruction(instr)).getAUse() or
operand instanceof MemoryOperand
}
/**
* Holds if `instr` is an instruction that is not used by the dataflow library.
* Ignored instructions are not recognized as reads/writes by SSA, and they
* don't have a corresponding `(Indirect)InstructionNode`.
*/
predicate ignoreInstruction(Instruction instr) {
DataFlowImplCommon::forceCachingInSameStage() and
(
instr instanceof WriteSideEffectInstruction or
instr instanceof PhiInstruction or
instr instanceof ReadSideEffectInstruction or
instr instanceof ChiInstruction or
instr instanceof InitializeIndirectionInstruction
)
}
/**
* Gets the C++ type of `this` in the member function `f`.
* The result is a glvalue if `isGLValue` is true, and
* a prvalue if `isGLValue` is false.
*/
bindingset[isGLValue]
private CppType getThisType(Cpp::MemberFunction f, boolean isGLValue) {
result.hasType(f.getTypeOfThis(), isGLValue)
}
/**
* Gets the C++ type of the instruction `i`.
*
* This is equivalent to `i.getResultLanguageType()` with the exception
* of instructions that directly references a `this` IRVariable. In this
* case, `i.getResultLanguageType()` gives an unknown type, whereas the
* predicate gives the expected type (i.e., a potentially cv-qualified
* type `A*` where `A` is the declaring type of the member function that
* contains `i`).
*/
cached
CppType getResultLanguageType(Instruction i) {
if i.(VariableAddressInstruction).getIRVariable() instanceof IRThisVariable
then
if i.isGLValue()
then result = getThisType(i.getEnclosingFunction(), true)
else result = getThisType(i.getEnclosingFunction(), false)
else result = i.getResultLanguageType()
}
/**
* Gets the C++ type of the operand `operand`.
* This is equivalent to the type of the operand's defining instruction.
*
* See `getResultLanguageType` for a description of this behavior.
*/
CppType getLanguageType(Operand operand) { result = getResultLanguageType(operand.getDef()) }
/**
* Gets the maximum number of indirections a glvalue of type `type` can have.
* For example:
* - If `type = int`, the result is 1
* - If `type = MyStruct`, the result is 1
* - If `type = char*`, the result is 2
*/
int getMaxIndirectionsForType(Type type) {
result = countIndirectionsForCppType(getTypeForGLValue(type))
}
/**
* Gets the maximum number of indirections a value of type `type` can have.
*
* Note that this predicate is intended to be called on unspecified types
* (i.e., `countIndirections(e.getUnspecifiedType())`).
*/
private int countIndirections(Type t) {
result =
1 +
countIndirections([t.(Cpp::PointerType).getBaseType(), t.(Cpp::ReferenceType).getBaseType()])
or
not t instanceof Cpp::PointerType and
not t instanceof Cpp::ReferenceType and
result = 0
}
/**
* Gets the maximum number of indirections a value of C++
* type `langType` can have.
*/
int countIndirectionsForCppType(LanguageType langType) {
exists(Type type | langType.hasType(type, true) |
result = 1 + countIndirections(type.getUnspecifiedType())
)
or
exists(Type type | langType.hasType(type, false) |
result = countIndirections(type.getUnspecifiedType())
)
}
/**
* A `CallInstruction` that calls an allocation function such
* as `malloc` or `operator new`.
*/
class AllocationInstruction extends CallInstruction {
AllocationInstruction() { this.getStaticCallTarget() instanceof Cpp::AllocationFunction }
}
/**
* Holds if `i` is a base instruction that starts a sequence of uses
* of some variable that SSA can handle.
*
* This is either when `i` is a `VariableAddressInstruction` or when
* `i` is a fresh allocation produced by an `AllocationInstruction`.
*/
private predicate isSourceVariableBase(Instruction i) {
i instanceof VariableAddressInstruction or i instanceof AllocationInstruction
}
/**
* Holds if the value pointed to by `operand` can potentially be
* modified be the caller.
*/
predicate isModifiableByCall(ArgumentOperand operand) {
exists(CallInstruction call, int index, CppType type |
type = getLanguageType(operand) and
call.getArgumentOperand(index) = operand and
if index = -1
then not call.getStaticCallTarget() instanceof Cpp::ConstMemberFunction
else not SideEffects::isConstPointerLike(any(Type t | type.hasType(t, _)))
)
}
cached
private module Cached {
/**
* Holds if `op` is a use of an SSA variable rooted at `base` with `ind` number
* of indirections.
*
* `certain` is `true` if the operand is guaranteed to read the variable, and
* `indirectionIndex` specifies the number of loads required to read the variable.
*/
cached
predicate isUse(boolean certain, Operand op, Instruction base, int ind, int indirectionIndex) {
not ignoreOperand(op) and
certain = true and
exists(LanguageType type, int m, int ind0 |
type = getLanguageType(op) and
m = countIndirectionsForCppType(type) and
isUseImpl(op, base, ind0) and
ind = ind0 + [0 .. m] and
indirectionIndex = ind - ind0
)
}
/**
* Holds if `operand` is a use of an SSA variable rooted at `base`, and the
* path from `base` to `operand` passes through `ind` load-like instructions.
*/
private predicate isUseImpl(Operand operand, Instruction base, int ind) {
DataFlowImplCommon::forceCachingInSameStage() and
ind = 0 and
operand.getDef() = base and
isSourceVariableBase(base)
or
exists(Operand mid, Instruction instr |
isUseImpl(mid, base, ind) and
instr = operand.getDef() and
conversionFlow(mid, instr, false)
)
or
exists(int ind0 |
isUseImpl(operand.getDef().(LoadInstruction).getSourceAddressOperand(), base, ind0)
or
isUseImpl(operand.getDef().(InitializeParameterInstruction).getAnOperand(), base, ind0)
|
ind0 = ind - 1
)
}
/**
* Holds if `address` is an address of an SSA variable rooted at `base`,
* and `instr` is a definition of the SSA variable with `ind` number of indirections.
*
* `certain` is `true` if `instr` is guaranteed to write to the variable, and
* `indirectionIndex` specifies the number of loads required to read the variable
* after the write operation.
*/
cached
predicate isDef(
boolean certain, Instruction instr, Operand address, Instruction base, int ind,
int indirectionIndex
) {
certain = true and
exists(int ind0, CppType type, int m |
address =
[
instr.(StoreInstruction).getDestinationAddressOperand(),
instr.(InitializeParameterInstruction).getAnOperand(),
instr.(InitializeDynamicAllocationInstruction).getAllocationAddressOperand(),
instr.(UninitializedInstruction).getAnOperand()
]
|
isDefImpl(address, base, ind0) and
type = getLanguageType(address) and
m = countIndirectionsForCppType(type) and
ind = ind0 + [1 .. m] and
indirectionIndex = ind - (ind0 + 1)
)
}
/**
* Holds if `address` is a use of an SSA variable rooted at `base`, and the
* path from `base` to `address` passes through `ind` load-like instructions.
*
* Note: Unlike `isUseImpl`, this predicate recurses through pointer-arithmetic
* instructions.
*/
private predicate isDefImpl(Operand address, Instruction base, int ind) {
DataFlowImplCommon::forceCachingInSameStage() and
ind = 0 and
address.getDef() = base and
isSourceVariableBase(base)
or
exists(Operand mid, Instruction instr |
isDefImpl(mid, base, ind) and
instr = address.getDef() and
conversionFlow(mid, instr, _)
)
or
exists(int ind0 |
isDefImpl(address.getDef().(LoadInstruction).getSourceAddressOperand(), base, ind0)
or
isDefImpl(address.getDef().(InitializeParameterInstruction).getAnOperand(), base, ind0)
|
ind0 = ind - 1
)
}
}
import Cached
/**
* Inputs to the shared SSA library's parameterized module that is shared
* between the SSA pruning stage, and the final SSA stage.
*/
module InputSigCommon {
class BasicBlock = IRBlock;
BasicBlock getImmediateBasicBlockDominator(BasicBlock bb) { result.immediatelyDominates(bb) }
BasicBlock getABasicBlockSuccessor(BasicBlock bb) { result = bb.getASuccessor() }
class ExitBasicBlock extends IRBlock {
ExitBasicBlock() { this.getLastInstruction() instanceof ExitFunctionInstruction }
}
}

View File

@@ -1,208 +0,0 @@
private import semmle.code.cpp.ir.IR
private import experimental.semmle.code.cpp.ir.dataflow.DataFlow
private import ModelUtil
private import semmle.code.cpp.models.interfaces.DataFlow
private import semmle.code.cpp.models.interfaces.SideEffect
private import DataFlowUtil
private import DataFlowPrivate
private import semmle.code.cpp.models.Models
/**
* Holds if taint propagates from `nodeFrom` to `nodeTo` in exactly one local
* (intra-procedural) step.
*/
predicate localTaintStep(DataFlow::Node nodeFrom, DataFlow::Node nodeTo) {
DataFlow::localFlowStep(nodeFrom, nodeTo)
or
localAdditionalTaintStep(nodeFrom, nodeTo)
}
/**
* Holds if taint can flow in one local step from `nodeFrom` to `nodeTo` excluding
* local data flow steps. That is, `nodeFrom` and `nodeTo` are likely to represent
* different objects.
*/
cached
predicate localAdditionalTaintStep(DataFlow::Node nodeFrom, DataFlow::Node nodeTo) {
operandToInstructionTaintStep(nodeFrom.asOperand(), nodeTo.asInstruction())
or
modeledTaintStep(nodeFrom, nodeTo)
or
// Flow from `op` to `*op`.
exists(Operand operand, int indirectionIndex |
nodeHasOperand(nodeFrom, operand, indirectionIndex) and
nodeHasOperand(nodeTo, operand, indirectionIndex - 1)
)
or
// Flow from `instr` to `*instr`.
exists(Instruction instr, int indirectionIndex |
nodeHasInstruction(nodeFrom, instr, indirectionIndex) and
nodeHasInstruction(nodeTo, instr, indirectionIndex - 1)
)
or
// Flow from (the indirection of) an operand of a pointer arithmetic instruction to the
// indirection of the pointer arithmetic instruction. This provides flow from `source`
// in `x[source]` to the result of the associated load instruction.
exists(PointerArithmeticInstruction pai, int indirectionIndex |
nodeHasOperand(nodeFrom, pai.getAnOperand(), pragma[only_bind_into](indirectionIndex)) and
hasInstructionAndIndex(nodeTo, pai, indirectionIndex + 1)
)
}
/**
* Holds if taint propagates from `nodeFrom` to `nodeTo` in exactly one local
* (intra-procedural) step.
*/
private predicate operandToInstructionTaintStep(Operand opFrom, Instruction instrTo) {
// Taint can flow through expressions that alter the value but preserve
// more than one bit of it _or_ expressions that follow data through
// pointer indirections.
instrTo.getAnOperand() = opFrom and
(
instrTo instanceof ArithmeticInstruction
or
instrTo instanceof BitwiseInstruction
or
instrTo instanceof PointerArithmeticInstruction
)
or
// The `CopyInstruction` case is also present in non-taint data flow, but
// that uses `getDef` rather than `getAnyDef`. For taint, we want flow
// from a definition of `myStruct` to a `myStruct.myField` expression.
instrTo.(LoadInstruction).getSourceAddressOperand() = opFrom
or
// Unary instructions tend to preserve enough information in practice that we
// want taint to flow through.
// The exception is `FieldAddressInstruction`. Together with the rules below for
// `LoadInstruction`s and `ChiInstruction`s, flow through `FieldAddressInstruction`
// could cause flow into one field to come out an unrelated field.
// This would happen across function boundaries, where the IR would not be able to
// match loads to stores.
instrTo.(UnaryInstruction).getUnaryOperand() = opFrom and
(
not instrTo instanceof FieldAddressInstruction
or
instrTo.(FieldAddressInstruction).getField().getDeclaringType() instanceof Union
)
}
/**
* Holds if taint may propagate from `source` to `sink` in zero or more local
* (intra-procedural) steps.
*/
pragma[inline]
predicate localTaint(DataFlow::Node source, DataFlow::Node sink) { localTaintStep*(source, sink) }
/**
* Holds if taint can flow from `i1` to `i2` in zero or more
* local (intra-procedural) steps.
*/
pragma[inline]
predicate localInstructionTaint(Instruction i1, Instruction i2) {
localTaint(DataFlow::instructionNode(i1), DataFlow::instructionNode(i2))
}
/**
* Holds if taint can flow from `e1` to `e2` in zero or more
* local (intra-procedural) steps.
*/
pragma[inline]
predicate localExprTaint(Expr e1, Expr e2) {
localTaint(DataFlow::exprNode(e1), DataFlow::exprNode(e2))
}
/**
* Holds if the additional step from `src` to `sink` should be included in all
* global taint flow configurations.
*/
predicate defaultAdditionalTaintStep(DataFlow::Node src, DataFlow::Node sink) {
localAdditionalTaintStep(src, sink)
}
/**
* Holds if default `TaintTracking::Configuration`s should allow implicit reads
* of `c` at sinks and inputs to additional taint steps.
*/
bindingset[node]
predicate defaultImplicitTaintRead(DataFlow::Node node, DataFlow::Content c) { none() }
/**
* Holds if `node` should be a sanitizer in all global taint flow configurations
* but not in local taint.
*/
predicate defaultTaintSanitizer(DataFlow::Node node) { none() }
/**
* Holds if taint can flow from `instrIn` to `instrOut` through a call to a
* modeled function.
*/
predicate modeledTaintStep(DataFlow::Node nodeIn, DataFlow::Node nodeOut) {
// Normal taint steps
exists(CallInstruction call, TaintFunction func, FunctionInput modelIn, FunctionOutput modelOut |
call.getStaticCallTarget() = func and
func.hasTaintFlow(modelIn, modelOut)
|
(
nodeIn = callInput(call, modelIn)
or
exists(int n |
modelIn.isParameterDerefOrQualifierObject(n) and
if n = -1
then nodeIn = callInput(call, any(InQualifierAddress inQualifier))
else nodeIn = callInput(call, any(InParameter inParam | inParam.getIndex() = n))
)
) and
nodeOut = callOutput(call, modelOut)
or
exists(int d |
nodeIn = callInput(call, modelIn, d)
or
exists(int n |
d = 1 and
modelIn.isParameterDerefOrQualifierObject(n) and
if n = -1
then nodeIn = callInput(call, any(InQualifierAddress inQualifier))
else nodeIn = callInput(call, any(InParameter inParam | inParam.getIndex() = n))
)
|
call.getStaticCallTarget() = func and
func.hasTaintFlow(modelIn, modelOut) and
nodeOut = callOutput(call, modelOut, d)
)
)
or
// Taint flow from one argument to another and data flow from an argument to a
// return value. This happens in functions like `strcat` and `memcpy`. We
// could model this flow in two separate steps, but that would add reverse
// flow from the write side-effect to the call instruction, which may not be
// desirable.
exists(
CallInstruction call, Function func, FunctionInput modelIn, OutParameterDeref modelMidOut,
int indexMid, InParameter modelMidIn, OutReturnValue modelOut
|
nodeIn = callInput(call, modelIn) and
nodeOut = callOutput(call, modelOut) and
call.getStaticCallTarget() = func and
func.(TaintFunction).hasTaintFlow(modelIn, modelMidOut) and
func.(DataFlowFunction).hasDataFlow(modelMidIn, modelOut) and
modelMidOut.isParameterDeref(indexMid) and
modelMidIn.isParameter(indexMid)
)
or
// Taint flow from a pointer argument to an output, when the model specifies flow from the deref
// to that output, but the deref is not modeled in the IR for the caller.
exists(
CallInstruction call, DataFlow::SideEffectOperandNode indirectArgument, Function func,
FunctionInput modelIn, FunctionOutput modelOut
|
indirectArgument = callInput(call, modelIn) and
indirectArgument.getAddressOperand() = nodeIn.asOperand() and
call.getStaticCallTarget() = func and
(
func.(DataFlowFunction).hasDataFlow(modelIn, modelOut)
or
func.(TaintFunction).hasTaintFlow(modelIn, modelOut)
) and
nodeOut = callOutput(call, modelOut)
)
}

View File

@@ -1,314 +0,0 @@
/**
* This module defines an initial SSA pruning stage that doesn't take
* indirections into account.
*/
private import codeql.ssa.Ssa as SsaImplCommon
private import semmle.code.cpp.ir.IR
private import experimental.semmle.code.cpp.ir.dataflow.internal.DataFlowImplCommon as DataFlowImplCommon
private import semmle.code.cpp.models.interfaces.Allocation as Alloc
private import semmle.code.cpp.models.interfaces.DataFlow as DataFlow
private import semmle.code.cpp.ir.implementation.raw.internal.SideEffects as SideEffects
private import semmle.code.cpp.ir.internal.IRCppLanguage
private import experimental.semmle.code.cpp.ir.dataflow.internal.DataFlowPrivate
private import experimental.semmle.code.cpp.ir.dataflow.internal.DataFlowUtil
private import experimental.semmle.code.cpp.ir.dataflow.internal.SsaInternalsCommon
private module SourceVariables {
newtype TBaseSourceVariable =
// Each IR variable gets its own source variable
TBaseIRVariable(IRVariable var) or
// Each allocation gets its own source variable
TBaseCallVariable(AllocationInstruction call)
abstract class BaseSourceVariable extends TBaseSourceVariable {
abstract string toString();
abstract DataFlowType getType();
}
class BaseIRVariable extends BaseSourceVariable, TBaseIRVariable {
IRVariable var;
IRVariable getIRVariable() { result = var }
BaseIRVariable() { this = TBaseIRVariable(var) }
override string toString() { result = var.toString() }
override DataFlowType getType() { result = var.getType() }
}
class BaseCallVariable extends BaseSourceVariable, TBaseCallVariable {
AllocationInstruction call;
BaseCallVariable() { this = TBaseCallVariable(call) }
AllocationInstruction getCallInstruction() { result = call }
override string toString() { result = call.toString() }
override DataFlowType getType() { result = call.getResultType() }
}
private newtype TSourceVariable =
TSourceIRVariable(BaseIRVariable baseVar) or
TCallVariable(AllocationInstruction call)
abstract class SourceVariable extends TSourceVariable {
abstract string toString();
abstract BaseSourceVariable getBaseVariable();
}
class SourceIRVariable extends SourceVariable, TSourceIRVariable {
BaseIRVariable var;
SourceIRVariable() { this = TSourceIRVariable(var) }
IRVariable getIRVariable() { result = var.getIRVariable() }
override BaseIRVariable getBaseVariable() { result.getIRVariable() = this.getIRVariable() }
override string toString() { result = this.getIRVariable().toString() }
}
class CallVariable extends SourceVariable, TCallVariable {
AllocationInstruction call;
CallVariable() { this = TCallVariable(call) }
AllocationInstruction getCall() { result = call }
override BaseCallVariable getBaseVariable() { result.getCallInstruction() = call }
override string toString() { result = "Call" }
}
}
import SourceVariables
private newtype TDefOrUseImpl =
TDefImpl(Operand address) { isDef(_, _, address, _, _, _) } or
TUseImpl(Operand operand) {
isUse(_, operand, _, _, _) and
not isDef(_, _, operand, _, _, _)
}
abstract private class DefOrUseImpl extends TDefOrUseImpl {
/** Gets a textual representation of this element. */
abstract string toString();
/** Gets the block of this definition or use. */
abstract IRBlock getBlock();
/** Holds if this definition or use has index `index` in block `block`. */
abstract predicate hasIndexInBlock(IRBlock block, int index);
final predicate hasIndexInBlock(IRBlock block, int index, SourceVariable sv) {
this.hasIndexInBlock(block, index) and
sv = this.getSourceVariable()
}
/** Gets the location of this element. */
abstract Cpp::Location getLocation();
abstract Instruction getBase();
final BaseSourceVariable getBaseSourceVariable() {
exists(IRVariable var |
result.(BaseIRVariable).getIRVariable() = var and
instructionHasIRVariable(this.getBase(), var)
)
or
result.(BaseCallVariable).getCallInstruction() = this.getBase()
}
/** Gets the variable that is defined or used. */
final SourceVariable getSourceVariable() {
exists(BaseSourceVariable v |
sourceVariableHasBaseAndIndex(result, v) and
defOrUseHasSourceVariable(this, v)
)
}
}
pragma[noinline]
private predicate instructionHasIRVariable(VariableAddressInstruction vai, IRVariable var) {
vai.getIRVariable() = var
}
private predicate defOrUseHasSourceVariable(DefOrUseImpl defOrUse, BaseSourceVariable bv) {
defHasSourceVariable(defOrUse, bv)
or
useHasSourceVariable(defOrUse, bv)
}
pragma[noinline]
private predicate defHasSourceVariable(DefImpl def, BaseSourceVariable bv) {
bv = def.getBaseSourceVariable()
}
pragma[noinline]
private predicate useHasSourceVariable(UseImpl use, BaseSourceVariable bv) {
bv = use.getBaseSourceVariable()
}
pragma[noinline]
private predicate sourceVariableHasBaseAndIndex(SourceVariable v, BaseSourceVariable bv) {
v.getBaseVariable() = bv
}
class DefImpl extends DefOrUseImpl, TDefImpl {
Operand address;
DefImpl() { this = TDefImpl(address) }
override Instruction getBase() { isDef(_, _, address, result, _, _) }
Operand getAddressOperand() { result = address }
Instruction getDefiningInstruction() { isDef(_, result, address, _, _, _) }
override string toString() { result = address.toString() }
override IRBlock getBlock() { result = this.getDefiningInstruction().getBlock() }
override Cpp::Location getLocation() { result = this.getDefiningInstruction().getLocation() }
final override predicate hasIndexInBlock(IRBlock block, int index) {
this.getDefiningInstruction() = block.getInstruction(index)
}
predicate isCertain() { isDef(true, _, address, _, _, _) }
}
class UseImpl extends DefOrUseImpl, TUseImpl {
Operand operand;
UseImpl() { this = TUseImpl(operand) }
Operand getOperand() { result = operand }
override string toString() { result = operand.toString() }
final override predicate hasIndexInBlock(IRBlock block, int index) {
operand.getUse() = block.getInstruction(index)
}
final override IRBlock getBlock() { result = operand.getUse().getBlock() }
final override Cpp::Location getLocation() { result = operand.getLocation() }
override Instruction getBase() { isUse(_, operand, result, _, _) }
predicate isCertain() { isUse(true, operand, _, _, _) }
}
private module SsaInput implements SsaImplCommon::InputSig {
import InputSigCommon
import SourceVariables
/**
* Holds if the `i`'th write in block `bb` writes to the variable `v`.
* `certain` is `true` if the write is guaranteed to overwrite the entire variable.
*/
predicate variableWrite(IRBlock bb, int i, SourceVariable v, boolean certain) {
DataFlowImplCommon::forceCachingInSameStage() and
exists(DefImpl def | def.hasIndexInBlock(bb, i, v) |
if def.isCertain() then certain = true else certain = false
)
}
/**
* Holds if the `i`'th read in block `bb` reads to the variable `v`.
* `certain` is `true` if the read is guaranteed.
*/
predicate variableRead(IRBlock bb, int i, SourceVariable v, boolean certain) {
exists(UseImpl use | use.hasIndexInBlock(bb, i, v) |
if use.isCertain() then certain = true else certain = false
)
}
}
private newtype TSsaDefOrUse =
TDefOrUse(DefOrUseImpl defOrUse) {
defOrUse instanceof UseImpl
or
// If `defOrUse` is a definition we only include it if the
// SSA library concludes that it's live after the write.
exists(Definition def, SourceVariable sv, IRBlock bb, int i |
def.definesAt(sv, bb, i) and
defOrUse.(DefImpl).hasIndexInBlock(bb, i, sv)
)
} or
TPhi(PhiNode phi)
abstract private class SsaDefOrUse extends TSsaDefOrUse {
string toString() { result = "SsaDefOrUse" }
DefOrUseImpl asDefOrUse() { none() }
PhiNode asPhi() { none() }
abstract Location getLocation();
}
class DefOrUse extends TDefOrUse, SsaDefOrUse {
DefOrUseImpl defOrUse;
DefOrUse() { this = TDefOrUse(defOrUse) }
final override DefOrUseImpl asDefOrUse() { result = defOrUse }
final override Location getLocation() { result = defOrUse.getLocation() }
final SourceVariable getSourceVariable() { result = defOrUse.getSourceVariable() }
}
class Phi extends TPhi, SsaDefOrUse {
PhiNode phi;
Phi() { this = TPhi(phi) }
final override PhiNode asPhi() { result = phi }
final override Location getLocation() { result = phi.getBasicBlock().getLocation() }
}
class UseOrPhi extends SsaDefOrUse {
UseOrPhi() {
this.asDefOrUse() instanceof UseImpl
or
this instanceof Phi
}
final override Location getLocation() {
result = this.asDefOrUse().getLocation() or result = this.(Phi).getLocation()
}
override string toString() {
result = this.asDefOrUse().toString()
or
this instanceof Phi and
result = "Phi"
}
}
class Def extends DefOrUse {
override DefImpl defOrUse;
Operand getAddressOperand() { result = defOrUse.getAddressOperand() }
Instruction getAddress() { result = this.getAddressOperand().getDef() }
Instruction getDefiningInstruction() { result = defOrUse.getDefiningInstruction() }
override string toString() { result = this.asDefOrUse().toString() + " (def)" }
}
private module SsaImpl = SsaImplCommon::Make<SsaInput>;
class PhiNode = SsaImpl::PhiNode;
class Definition = SsaImpl::Definition;

View File

@@ -1,191 +0,0 @@
/**
* Provides an implementation of global (interprocedural) taint tracking.
* This file re-exports the local (intraprocedural) taint-tracking analysis
* from `TaintTrackingParameter::Public` and adds a global analysis, mainly
* exposed through the `Configuration` class. For some languages, this file
* exists in several identical copies, allowing queries to use multiple
* `Configuration` classes that depend on each other without introducing
* mutual recursion among those configurations.
*/
import TaintTrackingParameter::Public
private import TaintTrackingParameter::Private
/**
* A configuration of interprocedural taint tracking analysis. This defines
* sources, sinks, and any other configurable aspect of the analysis. Each
* use of the taint tracking library must define its own unique extension of
* this abstract class.
*
* A taint-tracking configuration is a special data flow configuration
* (`DataFlow::Configuration`) that allows for flow through nodes that do not
* necessarily preserve values but are still relevant from a taint tracking
* perspective. (For example, string concatenation, where one of the operands
* is tainted.)
*
* To create a configuration, extend this class with a subclass whose
* characteristic predicate is a unique singleton string. For example, write
*
* ```ql
* class MyAnalysisConfiguration extends TaintTracking::Configuration {
* MyAnalysisConfiguration() { this = "MyAnalysisConfiguration" }
* // Override `isSource` and `isSink`.
* // Optionally override `isSanitizer`.
* // Optionally override `isSanitizerIn`.
* // Optionally override `isSanitizerOut`.
* // Optionally override `isSanitizerGuard`.
* // Optionally override `isAdditionalTaintStep`.
* }
* ```
*
* Then, to query whether there is flow between some `source` and `sink`,
* write
*
* ```ql
* exists(MyAnalysisConfiguration cfg | cfg.hasFlow(source, sink))
* ```
*
* Multiple configurations can coexist, but it is unsupported to depend on
* another `TaintTracking::Configuration` or a `DataFlow::Configuration` in the
* overridden predicates that define sources, sinks, or additional steps.
* Instead, the dependency should go to a `TaintTracking2::Configuration` or a
* `DataFlow2::Configuration`, `DataFlow3::Configuration`, etc.
*/
abstract class Configuration extends DataFlow::Configuration {
bindingset[this]
Configuration() { any() }
/**
* Holds if `source` is a relevant taint source.
*
* The smaller this predicate is, the faster `hasFlow()` will converge.
*/
// overridden to provide taint-tracking specific qldoc
override predicate isSource(DataFlow::Node source) { none() }
/**
* Holds if `source` is a relevant taint source with the given initial
* `state`.
*
* The smaller this predicate is, the faster `hasFlow()` will converge.
*/
// overridden to provide taint-tracking specific qldoc
override predicate isSource(DataFlow::Node source, DataFlow::FlowState state) { none() }
/**
* Holds if `sink` is a relevant taint sink
*
* The smaller this predicate is, the faster `hasFlow()` will converge.
*/
// overridden to provide taint-tracking specific qldoc
override predicate isSink(DataFlow::Node sink) { none() }
/**
* Holds if `sink` is a relevant taint sink accepting `state`.
*
* The smaller this predicate is, the faster `hasFlow()` will converge.
*/
// overridden to provide taint-tracking specific qldoc
override predicate isSink(DataFlow::Node sink, DataFlow::FlowState state) { none() }
/** Holds if the node `node` is a taint sanitizer. */
predicate isSanitizer(DataFlow::Node node) { none() }
final override predicate isBarrier(DataFlow::Node node) {
this.isSanitizer(node) or
defaultTaintSanitizer(node)
}
/**
* Holds if the node `node` is a taint sanitizer when the flow state is
* `state`.
*/
predicate isSanitizer(DataFlow::Node node, DataFlow::FlowState state) { none() }
final override predicate isBarrier(DataFlow::Node node, DataFlow::FlowState state) {
this.isSanitizer(node, state)
}
/** Holds if taint propagation into `node` is prohibited. */
predicate isSanitizerIn(DataFlow::Node node) { none() }
final override predicate isBarrierIn(DataFlow::Node node) { this.isSanitizerIn(node) }
/** Holds if taint propagation out of `node` is prohibited. */
predicate isSanitizerOut(DataFlow::Node node) { none() }
final override predicate isBarrierOut(DataFlow::Node node) { this.isSanitizerOut(node) }
/**
* DEPRECATED: Use `isSanitizer` and `BarrierGuard` module instead.
*
* Holds if taint propagation through nodes guarded by `guard` is prohibited.
*/
deprecated predicate isSanitizerGuard(DataFlow::BarrierGuard guard) { none() }
deprecated final override predicate isBarrierGuard(DataFlow::BarrierGuard guard) {
this.isSanitizerGuard(guard)
}
/**
* DEPRECATED: Use `isSanitizer` and `BarrierGuard` module instead.
*
* Holds if taint propagation through nodes guarded by `guard` is prohibited
* when the flow state is `state`.
*/
deprecated predicate isSanitizerGuard(DataFlow::BarrierGuard guard, DataFlow::FlowState state) {
none()
}
deprecated final override predicate isBarrierGuard(
DataFlow::BarrierGuard guard, DataFlow::FlowState state
) {
this.isSanitizerGuard(guard, state)
}
/**
* Holds if taint may propagate from `node1` to `node2` in addition to the normal data-flow and taint steps.
*/
predicate isAdditionalTaintStep(DataFlow::Node node1, DataFlow::Node node2) { none() }
final override predicate isAdditionalFlowStep(DataFlow::Node node1, DataFlow::Node node2) {
this.isAdditionalTaintStep(node1, node2) or
defaultAdditionalTaintStep(node1, node2)
}
/**
* Holds if taint may propagate from `node1` to `node2` in addition to the normal data-flow and taint steps.
* This step is only applicable in `state1` and updates the flow state to `state2`.
*/
predicate isAdditionalTaintStep(
DataFlow::Node node1, DataFlow::FlowState state1, DataFlow::Node node2,
DataFlow::FlowState state2
) {
none()
}
final override predicate isAdditionalFlowStep(
DataFlow::Node node1, DataFlow::FlowState state1, DataFlow::Node node2,
DataFlow::FlowState state2
) {
this.isAdditionalTaintStep(node1, state1, node2, state2)
}
override predicate allowImplicitRead(DataFlow::Node node, DataFlow::ContentSet c) {
(
this.isSink(node) or
this.isSink(node, _) or
this.isAdditionalTaintStep(node, _) or
this.isAdditionalTaintStep(node, _, _, _)
) and
defaultImplicitTaintRead(node, c)
}
/**
* Holds if taint may flow from `source` to `sink` for this configuration.
*/
// overridden to provide taint-tracking specific qldoc
override predicate hasFlow(DataFlow::Node source, DataFlow::Node sink) {
super.hasFlow(source, sink)
}
}

View File

@@ -1,5 +0,0 @@
import experimental.semmle.code.cpp.ir.dataflow.internal.TaintTrackingUtil as Public
module Private {
import experimental.semmle.code.cpp.ir.dataflow.DataFlow::DataFlow as DataFlow
}

View File

@@ -1,191 +0,0 @@
/**
* Provides an implementation of global (interprocedural) taint tracking.
* This file re-exports the local (intraprocedural) taint-tracking analysis
* from `TaintTrackingParameter::Public` and adds a global analysis, mainly
* exposed through the `Configuration` class. For some languages, this file
* exists in several identical copies, allowing queries to use multiple
* `Configuration` classes that depend on each other without introducing
* mutual recursion among those configurations.
*/
import TaintTrackingParameter::Public
private import TaintTrackingParameter::Private
/**
* A configuration of interprocedural taint tracking analysis. This defines
* sources, sinks, and any other configurable aspect of the analysis. Each
* use of the taint tracking library must define its own unique extension of
* this abstract class.
*
* A taint-tracking configuration is a special data flow configuration
* (`DataFlow::Configuration`) that allows for flow through nodes that do not
* necessarily preserve values but are still relevant from a taint tracking
* perspective. (For example, string concatenation, where one of the operands
* is tainted.)
*
* To create a configuration, extend this class with a subclass whose
* characteristic predicate is a unique singleton string. For example, write
*
* ```ql
* class MyAnalysisConfiguration extends TaintTracking::Configuration {
* MyAnalysisConfiguration() { this = "MyAnalysisConfiguration" }
* // Override `isSource` and `isSink`.
* // Optionally override `isSanitizer`.
* // Optionally override `isSanitizerIn`.
* // Optionally override `isSanitizerOut`.
* // Optionally override `isSanitizerGuard`.
* // Optionally override `isAdditionalTaintStep`.
* }
* ```
*
* Then, to query whether there is flow between some `source` and `sink`,
* write
*
* ```ql
* exists(MyAnalysisConfiguration cfg | cfg.hasFlow(source, sink))
* ```
*
* Multiple configurations can coexist, but it is unsupported to depend on
* another `TaintTracking::Configuration` or a `DataFlow::Configuration` in the
* overridden predicates that define sources, sinks, or additional steps.
* Instead, the dependency should go to a `TaintTracking2::Configuration` or a
* `DataFlow2::Configuration`, `DataFlow3::Configuration`, etc.
*/
abstract class Configuration extends DataFlow::Configuration {
bindingset[this]
Configuration() { any() }
/**
* Holds if `source` is a relevant taint source.
*
* The smaller this predicate is, the faster `hasFlow()` will converge.
*/
// overridden to provide taint-tracking specific qldoc
override predicate isSource(DataFlow::Node source) { none() }
/**
* Holds if `source` is a relevant taint source with the given initial
* `state`.
*
* The smaller this predicate is, the faster `hasFlow()` will converge.
*/
// overridden to provide taint-tracking specific qldoc
override predicate isSource(DataFlow::Node source, DataFlow::FlowState state) { none() }
/**
* Holds if `sink` is a relevant taint sink
*
* The smaller this predicate is, the faster `hasFlow()` will converge.
*/
// overridden to provide taint-tracking specific qldoc
override predicate isSink(DataFlow::Node sink) { none() }
/**
* Holds if `sink` is a relevant taint sink accepting `state`.
*
* The smaller this predicate is, the faster `hasFlow()` will converge.
*/
// overridden to provide taint-tracking specific qldoc
override predicate isSink(DataFlow::Node sink, DataFlow::FlowState state) { none() }
/** Holds if the node `node` is a taint sanitizer. */
predicate isSanitizer(DataFlow::Node node) { none() }
final override predicate isBarrier(DataFlow::Node node) {
this.isSanitizer(node) or
defaultTaintSanitizer(node)
}
/**
* Holds if the node `node` is a taint sanitizer when the flow state is
* `state`.
*/
predicate isSanitizer(DataFlow::Node node, DataFlow::FlowState state) { none() }
final override predicate isBarrier(DataFlow::Node node, DataFlow::FlowState state) {
this.isSanitizer(node, state)
}
/** Holds if taint propagation into `node` is prohibited. */
predicate isSanitizerIn(DataFlow::Node node) { none() }
final override predicate isBarrierIn(DataFlow::Node node) { this.isSanitizerIn(node) }
/** Holds if taint propagation out of `node` is prohibited. */
predicate isSanitizerOut(DataFlow::Node node) { none() }
final override predicate isBarrierOut(DataFlow::Node node) { this.isSanitizerOut(node) }
/**
* DEPRECATED: Use `isSanitizer` and `BarrierGuard` module instead.
*
* Holds if taint propagation through nodes guarded by `guard` is prohibited.
*/
deprecated predicate isSanitizerGuard(DataFlow::BarrierGuard guard) { none() }
deprecated final override predicate isBarrierGuard(DataFlow::BarrierGuard guard) {
this.isSanitizerGuard(guard)
}
/**
* DEPRECATED: Use `isSanitizer` and `BarrierGuard` module instead.
*
* Holds if taint propagation through nodes guarded by `guard` is prohibited
* when the flow state is `state`.
*/
deprecated predicate isSanitizerGuard(DataFlow::BarrierGuard guard, DataFlow::FlowState state) {
none()
}
deprecated final override predicate isBarrierGuard(
DataFlow::BarrierGuard guard, DataFlow::FlowState state
) {
this.isSanitizerGuard(guard, state)
}
/**
* Holds if taint may propagate from `node1` to `node2` in addition to the normal data-flow and taint steps.
*/
predicate isAdditionalTaintStep(DataFlow::Node node1, DataFlow::Node node2) { none() }
final override predicate isAdditionalFlowStep(DataFlow::Node node1, DataFlow::Node node2) {
this.isAdditionalTaintStep(node1, node2) or
defaultAdditionalTaintStep(node1, node2)
}
/**
* Holds if taint may propagate from `node1` to `node2` in addition to the normal data-flow and taint steps.
* This step is only applicable in `state1` and updates the flow state to `state2`.
*/
predicate isAdditionalTaintStep(
DataFlow::Node node1, DataFlow::FlowState state1, DataFlow::Node node2,
DataFlow::FlowState state2
) {
none()
}
final override predicate isAdditionalFlowStep(
DataFlow::Node node1, DataFlow::FlowState state1, DataFlow::Node node2,
DataFlow::FlowState state2
) {
this.isAdditionalTaintStep(node1, state1, node2, state2)
}
override predicate allowImplicitRead(DataFlow::Node node, DataFlow::ContentSet c) {
(
this.isSink(node) or
this.isSink(node, _) or
this.isAdditionalTaintStep(node, _) or
this.isAdditionalTaintStep(node, _, _, _)
) and
defaultImplicitTaintRead(node, c)
}
/**
* Holds if taint may flow from `source` to `sink` for this configuration.
*/
// overridden to provide taint-tracking specific qldoc
override predicate hasFlow(DataFlow::Node source, DataFlow::Node sink) {
super.hasFlow(source, sink)
}
}

View File

@@ -1,5 +0,0 @@
import experimental.semmle.code.cpp.ir.dataflow.internal.TaintTrackingUtil as Public
module Private {
import experimental.semmle.code.cpp.ir.dataflow.DataFlow2::DataFlow2 as DataFlow
}

View File

@@ -1,191 +0,0 @@
/**
* Provides an implementation of global (interprocedural) taint tracking.
* This file re-exports the local (intraprocedural) taint-tracking analysis
* from `TaintTrackingParameter::Public` and adds a global analysis, mainly
* exposed through the `Configuration` class. For some languages, this file
* exists in several identical copies, allowing queries to use multiple
* `Configuration` classes that depend on each other without introducing
* mutual recursion among those configurations.
*/
import TaintTrackingParameter::Public
private import TaintTrackingParameter::Private
/**
* A configuration of interprocedural taint tracking analysis. This defines
* sources, sinks, and any other configurable aspect of the analysis. Each
* use of the taint tracking library must define its own unique extension of
* this abstract class.
*
* A taint-tracking configuration is a special data flow configuration
* (`DataFlow::Configuration`) that allows for flow through nodes that do not
* necessarily preserve values but are still relevant from a taint tracking
* perspective. (For example, string concatenation, where one of the operands
* is tainted.)
*
* To create a configuration, extend this class with a subclass whose
* characteristic predicate is a unique singleton string. For example, write
*
* ```ql
* class MyAnalysisConfiguration extends TaintTracking::Configuration {
* MyAnalysisConfiguration() { this = "MyAnalysisConfiguration" }
* // Override `isSource` and `isSink`.
* // Optionally override `isSanitizer`.
* // Optionally override `isSanitizerIn`.
* // Optionally override `isSanitizerOut`.
* // Optionally override `isSanitizerGuard`.
* // Optionally override `isAdditionalTaintStep`.
* }
* ```
*
* Then, to query whether there is flow between some `source` and `sink`,
* write
*
* ```ql
* exists(MyAnalysisConfiguration cfg | cfg.hasFlow(source, sink))
* ```
*
* Multiple configurations can coexist, but it is unsupported to depend on
* another `TaintTracking::Configuration` or a `DataFlow::Configuration` in the
* overridden predicates that define sources, sinks, or additional steps.
* Instead, the dependency should go to a `TaintTracking2::Configuration` or a
* `DataFlow2::Configuration`, `DataFlow3::Configuration`, etc.
*/
abstract class Configuration extends DataFlow::Configuration {
bindingset[this]
Configuration() { any() }
/**
* Holds if `source` is a relevant taint source.
*
* The smaller this predicate is, the faster `hasFlow()` will converge.
*/
// overridden to provide taint-tracking specific qldoc
override predicate isSource(DataFlow::Node source) { none() }
/**
* Holds if `source` is a relevant taint source with the given initial
* `state`.
*
* The smaller this predicate is, the faster `hasFlow()` will converge.
*/
// overridden to provide taint-tracking specific qldoc
override predicate isSource(DataFlow::Node source, DataFlow::FlowState state) { none() }
/**
* Holds if `sink` is a relevant taint sink
*
* The smaller this predicate is, the faster `hasFlow()` will converge.
*/
// overridden to provide taint-tracking specific qldoc
override predicate isSink(DataFlow::Node sink) { none() }
/**
* Holds if `sink` is a relevant taint sink accepting `state`.
*
* The smaller this predicate is, the faster `hasFlow()` will converge.
*/
// overridden to provide taint-tracking specific qldoc
override predicate isSink(DataFlow::Node sink, DataFlow::FlowState state) { none() }
/** Holds if the node `node` is a taint sanitizer. */
predicate isSanitizer(DataFlow::Node node) { none() }
final override predicate isBarrier(DataFlow::Node node) {
this.isSanitizer(node) or
defaultTaintSanitizer(node)
}
/**
* Holds if the node `node` is a taint sanitizer when the flow state is
* `state`.
*/
predicate isSanitizer(DataFlow::Node node, DataFlow::FlowState state) { none() }
final override predicate isBarrier(DataFlow::Node node, DataFlow::FlowState state) {
this.isSanitizer(node, state)
}
/** Holds if taint propagation into `node` is prohibited. */
predicate isSanitizerIn(DataFlow::Node node) { none() }
final override predicate isBarrierIn(DataFlow::Node node) { this.isSanitizerIn(node) }
/** Holds if taint propagation out of `node` is prohibited. */
predicate isSanitizerOut(DataFlow::Node node) { none() }
final override predicate isBarrierOut(DataFlow::Node node) { this.isSanitizerOut(node) }
/**
* DEPRECATED: Use `isSanitizer` and `BarrierGuard` module instead.
*
* Holds if taint propagation through nodes guarded by `guard` is prohibited.
*/
deprecated predicate isSanitizerGuard(DataFlow::BarrierGuard guard) { none() }
deprecated final override predicate isBarrierGuard(DataFlow::BarrierGuard guard) {
this.isSanitizerGuard(guard)
}
/**
* DEPRECATED: Use `isSanitizer` and `BarrierGuard` module instead.
*
* Holds if taint propagation through nodes guarded by `guard` is prohibited
* when the flow state is `state`.
*/
deprecated predicate isSanitizerGuard(DataFlow::BarrierGuard guard, DataFlow::FlowState state) {
none()
}
deprecated final override predicate isBarrierGuard(
DataFlow::BarrierGuard guard, DataFlow::FlowState state
) {
this.isSanitizerGuard(guard, state)
}
/**
* Holds if taint may propagate from `node1` to `node2` in addition to the normal data-flow and taint steps.
*/
predicate isAdditionalTaintStep(DataFlow::Node node1, DataFlow::Node node2) { none() }
final override predicate isAdditionalFlowStep(DataFlow::Node node1, DataFlow::Node node2) {
this.isAdditionalTaintStep(node1, node2) or
defaultAdditionalTaintStep(node1, node2)
}
/**
* Holds if taint may propagate from `node1` to `node2` in addition to the normal data-flow and taint steps.
* This step is only applicable in `state1` and updates the flow state to `state2`.
*/
predicate isAdditionalTaintStep(
DataFlow::Node node1, DataFlow::FlowState state1, DataFlow::Node node2,
DataFlow::FlowState state2
) {
none()
}
final override predicate isAdditionalFlowStep(
DataFlow::Node node1, DataFlow::FlowState state1, DataFlow::Node node2,
DataFlow::FlowState state2
) {
this.isAdditionalTaintStep(node1, state1, node2, state2)
}
override predicate allowImplicitRead(DataFlow::Node node, DataFlow::ContentSet c) {
(
this.isSink(node) or
this.isSink(node, _) or
this.isAdditionalTaintStep(node, _) or
this.isAdditionalTaintStep(node, _, _, _)
) and
defaultImplicitTaintRead(node, c)
}
/**
* Holds if taint may flow from `source` to `sink` for this configuration.
*/
// overridden to provide taint-tracking specific qldoc
override predicate hasFlow(DataFlow::Node source, DataFlow::Node sink) {
super.hasFlow(source, sink)
}
}

View File

@@ -1,5 +0,0 @@
import experimental.semmle.code.cpp.ir.dataflow.internal.TaintTrackingUtil as Public
module Private {
import experimental.semmle.code.cpp.ir.dataflow.DataFlow3::DataFlow3 as DataFlow
}

View File

@@ -37,7 +37,7 @@ abstract class SimpleRangeAnalysisDefinition extends RangeSsaDefinition {
* dependencies. Without this information, range analysis might work for
* simple cases but will go into infinite loops on complex code.
*
* For example, when modeling the definition by reference in a call to an
* For example, when modelling the definition by reference in a call to an
* overloaded `operator=`, written as `v = e`, the definition of `(this, v)`
* depends on `e`.
*/

View File

@@ -28,10 +28,6 @@ private newtype TBound =
i.(LoadInstruction).getSourceAddress() instanceof FieldAddressInstruction
or
i.getAUse() instanceof ArgumentOperand
or
i instanceof PointerArithmeticInstruction
or
i.getAUse() instanceof AddressOperand
)
}
@@ -77,7 +73,7 @@ class ValueNumberBound extends Bound, TBoundValueNumber {
this = TBoundValueNumber(valueNumber(result)) and delta = 0
}
override string toString() { result = "ValueNumberBound" }
override string toString() { result = vn.getExampleInstruction().toString() }
override Location getLocation() { result = vn.getLocation() }

View File

@@ -5,7 +5,7 @@
* `Instruction` level), and then using the array length analysis and the range
* analysis together to prove that some of these pointer dereferences are safe.
*
* The analysis is soundy, i.e. it is sound if no undefined behavior is present
* The analysis is soundy, i.e. it is sound if no undefined behaviour is present
* in the program.
* Furthermore, it crucially depends on the soundiness of the range analysis and
* the array length analysis.

View File

@@ -4,7 +4,7 @@
import cpp
import semmle.code.cpp.dataflow.TaintTracking
import semmle.code.cpp.security.PrivateData
import experimental.semmle.code.cpp.security.PrivateData
import semmle.code.cpp.security.FileWrite
import semmle.code.cpp.security.BufferWrite

View File

@@ -0,0 +1,52 @@
/**
* Provides classes and predicates for identifying private data and functions for security.
*
* 'Private' data in general is anything that would compromise user privacy if exposed. This
* library tries to guess where private data may either be stored in a variable or produced by a
* function.
*
* This library is not concerned with credentials. See `SensitiveActions` for expressions related
* to credentials.
*/
import cpp
/** A string for `match` that identifies strings that look like they represent private data. */
private string privateNames() {
result =
[
// Inspired by the list on https://cwe.mitre.org/data/definitions/359.html
// Government identifiers, such as Social Security Numbers
"%social%security%number%",
// Contact information, such as home addresses and telephone numbers
"%postcode%", "%zipcode%",
// result = "%telephone%" or
// Geographic location - where the user is (or was)
"%latitude%", "%longitude%",
// Financial data - such as credit card numbers, salary, bank accounts, and debts
"%creditcard%", "%salary%", "%bankaccount%",
// Communications - e-mail addresses, private e-mail messages, SMS text messages, chat logs, etc.
// result = "%email%" or
// result = "%mobile%" or
"%employer%",
// Health - medical conditions, insurance status, prescription records
"%medical%"
]
}
/** An expression that might contain private data. */
abstract class PrivateDataExpr extends Expr { }
/** A functiond call that might produce private data. */
class PrivateFunctionCall extends PrivateDataExpr, FunctionCall {
PrivateFunctionCall() {
exists(string s | this.getTarget().getName().toLowerCase() = s | s.matches(privateNames()))
}
}
/** An access to a variable that might contain private data. */
class PrivateVariableAccess extends PrivateDataExpr, VariableAccess {
PrivateVariableAccess() {
exists(string s | this.getTarget().getName().toLowerCase() = s | s.matches(privateNames()))
}
}

View File

@@ -1,7 +0,0 @@
import SemanticExpr
import SemanticBound
import SemanticSSA
import SemanticGuard
import SemanticCFG
import SemanticType
import SemanticOpcode

View File

@@ -1,42 +0,0 @@
/**
* Semantic wrapper around the language-specific bounds library.
*/
private import SemanticExpr
private import SemanticExprSpecific::SemanticExprConfig as Specific
private import SemanticSSA
/**
* A valid base for an expression bound.
*
* Can be either a variable (`SemSsaBound`) or zero (`SemZeroBound`).
*/
class SemBound instanceof Specific::Bound {
final string toString() { result = super.toString() }
final SemExpr getExpr(int delta) { result = Specific::getBoundExpr(this, delta) }
}
/**
* A bound that is a constant zero.
*/
class SemZeroBound extends SemBound {
SemZeroBound() { Specific::zeroBound(this) }
}
/**
* A bound that is an SSA definition.
*/
class SemSsaBound extends SemBound {
/**
* The variables whose value is used as the bound.
*
* Can be multi-valued in some implementations. If so, all variables will be equivalent.
*/
SemSsaVariable var;
SemSsaBound() { Specific::ssaBound(this, var) }
/** Gets a variable whose value is used as the bound. */
final SemSsaVariable getAVariable() { result = var }
}

View File

@@ -1,22 +0,0 @@
/**
* Semantic interface to the control flow graph.
*/
private import Semantic
private import SemanticExprSpecific::SemanticExprConfig as Specific
/**
* A basic block in the control-flow graph.
*/
class SemBasicBlock extends Specific::BasicBlock {
/** Holds if this block (transitively) dominates `otherblock`. */
final predicate bbDominates(SemBasicBlock otherBlock) { Specific::bbDominates(this, otherBlock) }
/** Holds if this block has dominance information. */
final predicate hasDominanceInformation() { Specific::hasDominanceInformation(this) }
/** Gets an expression that is evaluated in this basic block. */
final SemExpr getAnExpr() { result.getBasicBlock() = this }
final int getUniqueId() { result = Specific::getBasicBlockUniqueId(this) }
}

View File

@@ -1,309 +0,0 @@
/**
* Semantic interface for expressions.
*/
private import Semantic
private import SemanticExprSpecific::SemanticExprConfig as Specific
/**
* An language-neutral expression.
*
* The expression computes a value of type `getSemType()`. The actual computation is determined by
* the expression's opcode (`getOpcode()`).
*/
class SemExpr instanceof Specific::Expr {
final string toString() { result = super.toString() }
final Specific::Location getLocation() { result = super.getLocation() }
Opcode getOpcode() { result instanceof Opcode::Unknown }
SemType getSemType() { result = Specific::getUnknownExprType(this) }
final SemBasicBlock getBasicBlock() { result = Specific::getExprBasicBlock(this) }
}
/** An expression with an opcode other than `Unknown`. */
abstract private class SemKnownExpr extends SemExpr {
Opcode opcode;
SemType type;
final override Opcode getOpcode() { result = opcode }
final override SemType getSemType() { result = type }
}
/** An expression that returns a literal value. */
class SemLiteralExpr extends SemKnownExpr {
SemLiteralExpr() {
Specific::integerLiteral(this, type, _) and opcode instanceof Opcode::Constant
or
Specific::largeIntegerLiteral(this, type, _) and opcode instanceof Opcode::Constant
or
Specific::booleanLiteral(this, type, _) and opcode instanceof Opcode::Constant
or
Specific::floatingPointLiteral(this, type, _) and opcode instanceof Opcode::Constant
or
Specific::nullLiteral(this, type) and opcode instanceof Opcode::Constant
or
Specific::stringLiteral(this, type, _) and opcode instanceof Opcode::StringConstant
}
}
/** An expression that returns a numeric literal value. */
class SemNumericLiteralExpr extends SemLiteralExpr {
SemNumericLiteralExpr() {
Specific::integerLiteral(this, _, _)
or
Specific::largeIntegerLiteral(this, _, _)
or
Specific::floatingPointLiteral(this, _, _)
}
/**
* Gets an approximation of the value of the literal, as a `float`.
*
* If the value can be precisely represented as a `float`, the result will be exact. If the actual
* value cannot be precisely represented (for example, it is an integer with more than 53
* significant bits), then the result is an approximation.
*/
float getApproximateFloatValue() { none() }
}
/** An expression that returns an integer literal value. */
class SemIntegerLiteralExpr extends SemNumericLiteralExpr {
SemIntegerLiteralExpr() {
Specific::integerLiteral(this, _, _)
or
Specific::largeIntegerLiteral(this, _, _)
}
/**
* Gets the value of the literal, if it can be represented as an `int`.
*
* If the value is outside the range of an `int`, use `getApproximateFloatValue()` to get a value
* that is equal to the actual integer value, within rounding error.
*/
final int getIntValue() { Specific::integerLiteral(this, _, result) }
final override float getApproximateFloatValue() {
result = getIntValue()
or
Specific::largeIntegerLiteral(this, _, result)
}
}
/**
* An expression that returns a floating-point literal value.
*/
class SemFloatingPointLiteralExpr extends SemNumericLiteralExpr {
float value;
SemFloatingPointLiteralExpr() { Specific::floatingPointLiteral(this, _, value) }
final override float getApproximateFloatValue() { result = value }
/** Gets the value of the literal. */
final float getFloatValue() { result = value }
}
/**
* An expression that consumes two operands.
*/
class SemBinaryExpr extends SemKnownExpr {
SemExpr leftOperand;
SemExpr rightOperand;
SemBinaryExpr() { Specific::binaryExpr(this, opcode, type, leftOperand, rightOperand) }
/** Gets the left operand. */
final SemExpr getLeftOperand() { result = leftOperand }
/** Gets the right operand. */
final SemExpr getRightOperand() { result = rightOperand }
/** Holds if `a` and `b` are the two operands, in either order. */
final predicate hasOperands(SemExpr a, SemExpr b) {
a = getLeftOperand() and b = getRightOperand()
or
a = getRightOperand() and b = getLeftOperand()
}
/** Gets the two operands. */
final SemExpr getAnOperand() { result = getLeftOperand() or result = getRightOperand() }
}
/** An expression that performs and ordered comparison of two operands. */
class SemRelationalExpr extends SemBinaryExpr {
SemRelationalExpr() {
opcode instanceof Opcode::CompareLT
or
opcode instanceof Opcode::CompareLE
or
opcode instanceof Opcode::CompareGT
or
opcode instanceof Opcode::CompareGE
}
/**
* Get the operand that will be less than the other operand if the result of the comparison is
* `true`.
*
* For `x < y` or `x <= y`, this will return `x`.
* For `x > y` or `x >= y`, this will return `y`.`
*/
final SemExpr getLesserOperand() {
if opcode instanceof Opcode::CompareLT or opcode instanceof Opcode::CompareLE
then result = getLeftOperand()
else result = getRightOperand()
}
/**
* Get the operand that will be greater than the other operand if the result of the comparison is
* `true`.
*
* For `x < y` or `x <= y`, this will return `y`.
* For `x > y` or `x >= y`, this will return `x`.`
*/
final SemExpr getGreaterOperand() {
if opcode instanceof Opcode::CompareGT or opcode instanceof Opcode::CompareGE
then result = getLeftOperand()
else result = getRightOperand()
}
/** Holds if this comparison returns `false` if the two operands are equal. */
final predicate isStrict() {
opcode instanceof Opcode::CompareLT or opcode instanceof Opcode::CompareGT
}
}
class SemAddExpr extends SemBinaryExpr {
SemAddExpr() { opcode instanceof Opcode::Add or opcode instanceof Opcode::PointerAdd }
}
class SemSubExpr extends SemBinaryExpr {
SemSubExpr() { opcode instanceof Opcode::Sub or opcode instanceof Opcode::PointerSub }
}
class SemMulExpr extends SemBinaryExpr {
SemMulExpr() { opcode instanceof Opcode::Mul }
}
class SemDivExpr extends SemBinaryExpr {
SemDivExpr() { opcode instanceof Opcode::Div }
}
class SemRemExpr extends SemBinaryExpr {
SemRemExpr() { opcode instanceof Opcode::Rem }
}
class SemShiftLeftExpr extends SemBinaryExpr {
SemShiftLeftExpr() { opcode instanceof Opcode::ShiftLeft }
}
class SemShiftRightExpr extends SemBinaryExpr {
SemShiftRightExpr() { opcode instanceof Opcode::ShiftRight }
}
class SemShiftRightUnsignedExpr extends SemBinaryExpr {
SemShiftRightUnsignedExpr() { opcode instanceof Opcode::ShiftRightUnsigned }
}
class SemBitAndExpr extends SemBinaryExpr {
SemBitAndExpr() { opcode instanceof Opcode::BitAnd }
}
class SemBitOrExpr extends SemBinaryExpr {
SemBitOrExpr() { opcode instanceof Opcode::BitOr }
}
class SemBitXorExpr extends SemBinaryExpr {
SemBitXorExpr() { opcode instanceof Opcode::BitXor }
}
class SemUnaryExpr extends SemKnownExpr {
SemExpr operand;
SemUnaryExpr() { Specific::unaryExpr(this, opcode, type, operand) }
final SemExpr getOperand() { result = operand }
}
class SemBoxExpr extends SemUnaryExpr {
SemBoxExpr() { opcode instanceof Opcode::Box }
}
class SemUnboxExpr extends SemUnaryExpr {
SemUnboxExpr() { opcode instanceof Opcode::Unbox }
}
class SemConvertExpr extends SemUnaryExpr {
SemConvertExpr() { opcode instanceof Opcode::Convert }
}
class SemCopyValueExpr extends SemUnaryExpr {
SemCopyValueExpr() { opcode instanceof Opcode::CopyValue }
}
class SemNegateExpr extends SemUnaryExpr {
SemNegateExpr() { opcode instanceof Opcode::Negate }
}
class SemBitComplementExpr extends SemUnaryExpr {
SemBitComplementExpr() { opcode instanceof Opcode::BitComplement }
}
class SemLogicalNotExpr extends SemUnaryExpr {
SemLogicalNotExpr() { opcode instanceof Opcode::LogicalNot }
}
class SemAddOneExpr extends SemUnaryExpr {
SemAddOneExpr() { opcode instanceof Opcode::AddOne }
}
class SemSubOneExpr extends SemUnaryExpr {
SemSubOneExpr() { opcode instanceof Opcode::SubOne }
}
private class SemNullaryExpr extends SemKnownExpr {
SemNullaryExpr() { Specific::nullaryExpr(this, opcode, type) }
}
class SemInitializeParameterExpr extends SemNullaryExpr {
SemInitializeParameterExpr() { opcode instanceof Opcode::InitializeParameter }
}
class SemLoadExpr extends SemNullaryExpr {
SemLoadExpr() { opcode instanceof Opcode::Load }
final SemSsaVariable getDef() { result.getAUse() = this }
}
class SemSsaLoadExpr extends SemLoadExpr {
SemSsaLoadExpr() { exists(getDef()) }
}
class SemNonSsaLoadExpr extends SemLoadExpr {
SemNonSsaLoadExpr() { not exists(getDef()) }
}
class SemStoreExpr extends SemUnaryExpr {
SemStoreExpr() { opcode instanceof Opcode::Store }
}
class SemConditionalExpr extends SemKnownExpr {
SemExpr condition;
SemExpr trueResult;
SemExpr falseResult;
SemConditionalExpr() {
opcode instanceof Opcode::Conditional and
Specific::conditionalExpr(this, type, condition, trueResult, falseResult)
}
final SemExpr getBranchExpr(boolean branch) {
branch = true and result = trueResult
or
branch = false and result = falseResult
}
}

View File

@@ -1,360 +0,0 @@
/**
* C++-specific implementation of the semantic interface.
*/
private import cpp as Cpp
private import semmle.code.cpp.ir.IR as IR
private import Semantic
private import experimental.semmle.code.cpp.rangeanalysis.Bound as IRBound
private import semmle.code.cpp.controlflow.IRGuards as IRGuards
private import semmle.code.cpp.ir.ValueNumbering
module SemanticExprConfig {
class Location = Cpp::Location;
class Expr = IR::Instruction;
SemBasicBlock getExprBasicBlock(Expr e) { result = getSemanticBasicBlock(e.getBlock()) }
private predicate anyConstantExpr(Expr expr, SemType type, string value) {
exists(IR::ConstantInstruction instr | instr = expr |
type = getSemanticType(instr.getResultIRType()) and
value = instr.getValue()
)
}
predicate integerLiteral(Expr expr, SemIntegerType type, int value) {
exists(string valueString |
anyConstantExpr(expr, type, valueString) and
value = valueString.toInt()
)
}
predicate largeIntegerLiteral(Expr expr, SemIntegerType type, float approximateFloatValue) {
exists(string valueString |
anyConstantExpr(expr, type, valueString) and
not exists(valueString.toInt()) and
approximateFloatValue = valueString.toFloat()
)
}
predicate floatingPointLiteral(Expr expr, SemFloatingPointType type, float value) {
exists(string valueString |
anyConstantExpr(expr, type, valueString) and value = valueString.toFloat()
)
}
predicate booleanLiteral(Expr expr, SemBooleanType type, boolean value) {
exists(string valueString |
anyConstantExpr(expr, type, valueString) and
(
valueString = "true" and value = true
or
valueString = "false" and value = false
)
)
}
predicate nullLiteral(Expr expr, SemAddressType type) { anyConstantExpr(expr, type, _) }
predicate stringLiteral(Expr expr, SemType type, string value) {
anyConstantExpr(expr, type, value) and expr instanceof IR::StringConstantInstruction
}
predicate binaryExpr(Expr expr, Opcode opcode, SemType type, Expr leftOperand, Expr rightOperand) {
exists(IR::BinaryInstruction instr | instr = expr |
type = getSemanticType(instr.getResultIRType()) and
leftOperand = instr.getLeft() and
rightOperand = instr.getRight() and
// REVIEW: Merge the two `Opcode` types.
opcode.toString() = instr.getOpcode().toString()
)
}
predicate unaryExpr(Expr expr, Opcode opcode, SemType type, Expr operand) {
type = getSemanticType(expr.getResultIRType()) and
(
exists(IR::UnaryInstruction instr | instr = expr |
operand = instr.getUnary() and
// REVIEW: Merge the two operand types.
opcode.toString() = instr.getOpcode().toString()
)
or
exists(IR::StoreInstruction instr | instr = expr |
operand = instr.getSourceValue() and
opcode instanceof Opcode::Store
)
)
}
predicate nullaryExpr(Expr expr, Opcode opcode, SemType type) {
type = getSemanticType(expr.getResultIRType()) and
(
expr instanceof IR::LoadInstruction and opcode instanceof Opcode::Load
or
expr instanceof IR::InitializeParameterInstruction and
opcode instanceof Opcode::InitializeParameter
)
}
predicate conditionalExpr(
Expr expr, SemType type, Expr condition, Expr trueResult, Expr falseResult
) {
none()
}
SemType getUnknownExprType(Expr expr) { result = getSemanticType(expr.getResultIRType()) }
class BasicBlock = IR::IRBlock;
predicate bbDominates(BasicBlock dominator, BasicBlock dominated) {
dominator.dominates(dominated)
}
predicate hasDominanceInformation(BasicBlock block) { any() }
private predicate id(Cpp::Locatable x, Cpp::Locatable y) { x = y }
private predicate idOf(Cpp::Locatable x, int y) = equivalenceRelation(id/2)(x, y)
int getBasicBlockUniqueId(BasicBlock block) { idOf(block.getFirstInstruction().getAst(), result) }
newtype TSsaVariable =
TSsaInstruction(IR::Instruction instr) { instr.hasMemoryResult() } or
TSsaOperand(IR::Operand op) { op.isDefinitionInexact() } or
TSsaPointerArithmeticGuard(IR::PointerArithmeticInstruction instr) {
exists(Guard g, IR::Operand use | use = instr.getAUse() |
g.comparesLt(use, _, _, _, _) or
g.comparesLt(_, use, _, _, _) or
g.comparesEq(use, _, _, _, _) or
g.comparesEq(_, use, _, _, _)
)
}
class SsaVariable extends TSsaVariable {
string toString() { none() }
Location getLocation() { none() }
IR::Instruction asInstruction() { none() }
IR::PointerArithmeticInstruction asPointerArithGuard() { none() }
IR::Operand asOperand() { none() }
}
class SsaInstructionVariable extends SsaVariable, TSsaInstruction {
IR::Instruction instr;
SsaInstructionVariable() { this = TSsaInstruction(instr) }
final override string toString() { result = instr.toString() }
final override Location getLocation() { result = instr.getLocation() }
final override IR::Instruction asInstruction() { result = instr }
}
class SsaPointerArithmeticGuard extends SsaVariable, TSsaPointerArithmeticGuard {
IR::PointerArithmeticInstruction instr;
SsaPointerArithmeticGuard() { this = TSsaPointerArithmeticGuard(instr) }
final override string toString() { result = instr.toString() }
final override Location getLocation() { result = instr.getLocation() }
final override IR::PointerArithmeticInstruction asPointerArithGuard() { result = instr }
}
class SsaOperand extends SsaVariable, TSsaOperand {
IR::Operand op;
SsaOperand() { this = TSsaOperand(op) }
final override string toString() { result = op.toString() }
final override Location getLocation() { result = op.getLocation() }
final override IR::Operand asOperand() { result = op }
}
predicate explicitUpdate(SsaVariable v, Expr sourceExpr) { v.asInstruction() = sourceExpr }
predicate phi(SsaVariable v) { v.asInstruction() instanceof IR::PhiInstruction }
SsaVariable getAPhiInput(SsaVariable v) {
exists(IR::PhiInstruction instr | v.asInstruction() = instr |
result.asInstruction() = instr.getAnInput()
or
result.asOperand() = instr.getAnInputOperand()
)
}
Expr getAUse(SsaVariable v) {
result.(IR::LoadInstruction).getSourceValue() = v.asInstruction()
or
result = valueNumber(v.asPointerArithGuard()).getAnInstruction()
}
SemType getSsaVariableType(SsaVariable v) {
result = getSemanticType(v.asInstruction().getResultIRType())
}
BasicBlock getSsaVariableBasicBlock(SsaVariable v) {
result = v.asInstruction().getBlock()
or
result = v.asOperand().getUse().getBlock()
}
private newtype TReadPosition =
TReadPositionBlock(IR::IRBlock block) or
TReadPositionPhiInputEdge(IR::IRBlock pred, IR::IRBlock succ) {
exists(IR::PhiInputOperand input |
pred = input.getPredecessorBlock() and
succ = input.getUse().getBlock()
)
}
class SsaReadPosition extends TReadPosition {
string toString() { none() }
Location getLocation() { none() }
predicate hasRead(SsaVariable v) { none() }
}
private class SsaReadPositionBlock extends SsaReadPosition, TReadPositionBlock {
IR::IRBlock block;
SsaReadPositionBlock() { this = TReadPositionBlock(block) }
final override string toString() { result = block.toString() }
final override Location getLocation() { result = block.getLocation() }
final override predicate hasRead(SsaVariable v) {
exists(IR::Operand operand |
operand.getDef() = v.asInstruction() or
operand.getDef() = valueNumber(v.asPointerArithGuard()).getAnInstruction()
|
not operand instanceof IR::PhiInputOperand and
operand.getUse().getBlock() = block
)
}
}
private class SsaReadPositionPhiInputEdge extends SsaReadPosition, TReadPositionPhiInputEdge {
IR::IRBlock pred;
IR::IRBlock succ;
SsaReadPositionPhiInputEdge() { this = TReadPositionPhiInputEdge(pred, succ) }
final override string toString() { result = pred.toString() + "->" + succ.toString() }
final override Location getLocation() { result = succ.getLocation() }
final override predicate hasRead(SsaVariable v) {
exists(IR::PhiInputOperand operand |
operand.getDef() = v.asInstruction() or
operand.getDef() = valueNumber(v.asPointerArithGuard()).getAnInstruction()
|
operand.getPredecessorBlock() = pred and
operand.getUse().getBlock() = succ
)
}
}
predicate hasReadOfSsaVariable(SsaReadPosition pos, SsaVariable v) { pos.hasRead(v) }
predicate readBlock(SsaReadPosition pos, BasicBlock block) { pos = TReadPositionBlock(block) }
predicate phiInputEdge(SsaReadPosition pos, BasicBlock origBlock, BasicBlock phiBlock) {
pos = TReadPositionPhiInputEdge(origBlock, phiBlock)
}
predicate phiInput(SsaReadPosition pos, SsaVariable phi, SsaVariable input) {
exists(IR::PhiInputOperand operand |
pos = TReadPositionPhiInputEdge(operand.getPredecessorBlock(), operand.getUse().getBlock())
|
phi.asInstruction() = operand.getUse() and
(
input.asInstruction() = operand.getDef()
or
input.asOperand() = operand
)
)
}
class Bound instanceof IRBound::Bound {
string toString() { result = super.toString() }
final Location getLocation() { result = super.getLocation() }
}
private class ValueNumberBound extends Bound {
IRBound::ValueNumberBound bound;
ValueNumberBound() { bound = this }
override string toString() { result = bound.toString() }
}
predicate zeroBound(Bound bound) { bound instanceof IRBound::ZeroBound }
predicate ssaBound(Bound bound, SsaVariable v) {
v.asInstruction() = bound.(IRBound::ValueNumberBound).getValueNumber().getAnInstruction()
}
Expr getBoundExpr(Bound bound, int delta) {
result = bound.(IRBound::Bound).getInstruction(delta)
}
class Guard = IRGuards::IRGuardCondition;
predicate guard(Guard guard, BasicBlock block) { block = guard.getBlock() }
Expr getGuardAsExpr(Guard guard) { result = guard }
predicate equalityGuard(Guard guard, Expr e1, Expr e2, boolean polarity) {
guard.comparesEq(e1.getAUse(), e2.getAUse(), 0, true, polarity)
}
predicate guardDirectlyControlsBlock(Guard guard, BasicBlock controlled, boolean branch) {
guard.controls(controlled, branch)
}
predicate guardHasBranchEdge(Guard guard, BasicBlock bb1, BasicBlock bb2, boolean branch) {
guard.controlsEdge(bb1, bb2, branch)
}
Guard comparisonGuard(Expr e) { result = e }
predicate implies_v2(Guard g1, boolean b1, Guard g2, boolean b2) {
none() // TODO
}
}
SemExpr getSemanticExpr(IR::Instruction instr) { result = instr }
IR::Instruction getCppInstruction(SemExpr e) { e = result }
SemBasicBlock getSemanticBasicBlock(IR::IRBlock block) { result = block }
IR::IRBlock getCppBasicBlock(SemBasicBlock block) { block = result }
SemSsaVariable getSemanticSsaVariable(IR::Instruction instr) {
result.(SemanticExprConfig::SsaVariable).asInstruction() = instr
}
IR::Instruction getCppSsaVariableInstruction(SemSsaVariable var) {
var.(SemanticExprConfig::SsaVariable).asInstruction() = result
}
SemBound getSemanticBound(IRBound::Bound bound) { result = bound }
IRBound::Bound getCppBound(SemBound bound) { bound = result }
SemGuard getSemanticGuard(IRGuards::IRGuardCondition guard) { result = guard }
IRGuards::IRGuardCondition getCppGuard(SemGuard guard) { guard = result }

View File

@@ -1,65 +0,0 @@
/**
* Semantic interface to the guards library.
*/
private import Semantic
private import SemanticExprSpecific::SemanticExprConfig as Specific
class SemGuard instanceof Specific::Guard {
SemBasicBlock block;
SemGuard() { Specific::guard(this, block) }
final string toString() { result = super.toString() }
final Specific::Location getLocation() { result = super.getLocation() }
final predicate isEquality(SemExpr e1, SemExpr e2, boolean polarity) {
Specific::equalityGuard(this, e1, e2, polarity)
}
final predicate directlyControls(SemBasicBlock controlled, boolean branch) {
Specific::guardDirectlyControlsBlock(this, controlled, branch)
}
final predicate hasBranchEdge(SemBasicBlock bb1, SemBasicBlock bb2, boolean branch) {
Specific::guardHasBranchEdge(this, bb1, bb2, branch)
}
final SemBasicBlock getBasicBlock() { result = block }
final SemExpr asExpr() { result = Specific::getGuardAsExpr(this) }
}
predicate semImplies_v2(SemGuard g1, boolean b1, SemGuard g2, boolean b2) {
Specific::implies_v2(g1, b1, g2, b2)
}
/**
* Holds if `guard` directly controls the position `controlled` with the
* value `testIsTrue`.
*/
predicate semGuardDirectlyControlsSsaRead(
SemGuard guard, SemSsaReadPosition controlled, boolean testIsTrue
) {
guard.directlyControls(controlled.(SemSsaReadPositionBlock).getBlock(), testIsTrue)
or
exists(SemSsaReadPositionPhiInputEdge controlledEdge | controlledEdge = controlled |
guard.directlyControls(controlledEdge.getOrigBlock(), testIsTrue) or
guard.hasBranchEdge(controlledEdge.getOrigBlock(), controlledEdge.getPhiBlock(), testIsTrue)
)
}
/**
* Holds if `guard` controls the position `controlled` with the value `testIsTrue`.
*/
predicate semGuardControlsSsaRead(SemGuard guard, SemSsaReadPosition controlled, boolean testIsTrue) {
semGuardDirectlyControlsSsaRead(guard, controlled, testIsTrue)
or
exists(SemGuard guard0, boolean testIsTrue0 |
semImplies_v2(guard0, testIsTrue0, guard, testIsTrue) and
semGuardControlsSsaRead(guard0, controlled, testIsTrue0)
)
}
SemGuard semGetComparisonGuard(SemRelationalExpr e) { result = Specific::comparisonGuard(e) }

View File

@@ -1,187 +0,0 @@
/**
* Definitions of all possible opcodes for `SemExpr`.
*/
private newtype TOpcode =
TInitializeParameter() or
TCopyValue() or
TLoad() or
TStore() or
TAdd() or
TSub() or
TMul() or
TDiv() or
TRem() or
TNegate() or
TShiftLeft() or
TShiftRight() or
TShiftRightUnsigned() or // TODO: Based on type
TBitAnd() or
TBitOr() or
TBitXor() or
TBitComplement() or
TLogicalNot() or
TCompareEQ() or
TCompareNE() or
TCompareLT() or
TCompareGT() or
TCompareLE() or
TCompareGE() or
TPointerAdd() or
TPointerSub() or
TPointerDiff() or
TConvert() or
TConstant() or
TStringConstant() or
TAddOne() or // TODO: Combine with `TAdd`
TSubOne() or // TODO: Combine with `TSub`
TConditional() or // TODO: Represent as flow
TCall() or
TBox() or
TUnbox() or
TUnknown()
class Opcode extends TOpcode {
string toString() { result = "???" }
}
module Opcode {
class InitializeParameter extends Opcode, TInitializeParameter {
override string toString() { result = "InitializeParameter" }
}
class CopyValue extends Opcode, TCopyValue {
override string toString() { result = "CopyValue" }
}
class Load extends Opcode, TLoad {
override string toString() { result = "Load" }
}
class Store extends Opcode, TStore {
override string toString() { result = "Store" }
}
class Add extends Opcode, TAdd {
override string toString() { result = "Add" }
}
class PointerAdd extends Opcode, TPointerAdd {
override string toString() { result = "PointerAdd" }
}
class Sub extends Opcode, TSub {
override string toString() { result = "Sub" }
}
class PointerSub extends Opcode, TPointerSub {
override string toString() { result = "PointerSub" }
}
class Mul extends Opcode, TMul {
override string toString() { result = "Mul" }
}
class Div extends Opcode, TDiv {
override string toString() { result = "Div" }
}
class Rem extends Opcode, TRem {
override string toString() { result = "Rem" }
}
class Negate extends Opcode, TNegate {
override string toString() { result = "Negate" }
}
class ShiftLeft extends Opcode, TShiftLeft {
override string toString() { result = "ShiftLeft" }
}
class ShiftRight extends Opcode, TShiftRight {
override string toString() { result = "ShiftRight" }
}
class ShiftRightUnsigned extends Opcode, TShiftRightUnsigned {
override string toString() { result = "ShiftRightUnsigned" }
}
class BitAnd extends Opcode, TBitAnd {
override string toString() { result = "BitAnd" }
}
class BitOr extends Opcode, TBitOr {
override string toString() { result = "BitOr" }
}
class BitXor extends Opcode, TBitXor {
override string toString() { result = "BitXor" }
}
class BitComplement extends Opcode, TBitComplement {
override string toString() { result = "BitComplement" }
}
class LogicalNot extends Opcode, TLogicalNot {
override string toString() { result = "LogicalNot" }
}
class CompareEQ extends Opcode, TCompareEQ {
override string toString() { result = "CompareEQ" }
}
class CompareNE extends Opcode, TCompareNE {
override string toString() { result = "CompareNE" }
}
class CompareLT extends Opcode, TCompareLT {
override string toString() { result = "CompareLT" }
}
class CompareLE extends Opcode, TCompareLE {
override string toString() { result = "CompareLE" }
}
class CompareGT extends Opcode, TCompareGT {
override string toString() { result = "CompareGT" }
}
class CompareGE extends Opcode, TCompareGE {
override string toString() { result = "CompareGE" }
}
class Convert extends Opcode, TConvert {
override string toString() { result = "Convert" }
}
class AddOne extends Opcode, TAddOne {
override string toString() { result = "AddOne" }
}
class SubOne extends Opcode, TSubOne {
override string toString() { result = "SubOne" }
}
class Conditional extends Opcode, TConditional {
override string toString() { result = "Conditional" }
}
class Constant extends Opcode, TConstant {
override string toString() { result = "Constant" }
}
class StringConstant extends Opcode, TStringConstant {
override string toString() { result = "StringConstant" }
}
class Box extends Opcode, TBox {
override string toString() { result = "Box" }
}
class Unbox extends Opcode, TUnbox {
override string toString() { result = "Unbox" }
}
class Unknown extends Opcode, TUnknown {
override string toString() { result = "Unknown" }
}
}

View File

@@ -1,75 +0,0 @@
/**
* Semantic interface to the SSA library.
*/
private import Semantic
private import SemanticExprSpecific::SemanticExprConfig as Specific
class SemSsaVariable instanceof Specific::SsaVariable {
final string toString() { result = super.toString() }
final Specific::Location getLocation() { result = super.getLocation() }
final SemExpr getAUse() { result = Specific::getAUse(this) }
final SemType getType() { result = Specific::getSsaVariableType(this) }
final SemBasicBlock getBasicBlock() { result = Specific::getSsaVariableBasicBlock(this) }
}
class SemSsaExplicitUpdate extends SemSsaVariable {
SemExpr sourceExpr;
SemSsaExplicitUpdate() { Specific::explicitUpdate(this, sourceExpr) }
final SemExpr getSourceExpr() { result = sourceExpr }
}
class SemSsaPhiNode extends SemSsaVariable {
SemSsaPhiNode() { Specific::phi(this) }
final SemSsaVariable getAPhiInput() { result = Specific::getAPhiInput(this) }
}
class SemSsaReadPosition instanceof Specific::SsaReadPosition {
final string toString() { result = super.toString() }
final Specific::Location getLocation() { result = super.getLocation() }
final predicate hasReadOfVar(SemSsaVariable var) { Specific::hasReadOfSsaVariable(this, var) }
}
class SemSsaReadPositionPhiInputEdge extends SemSsaReadPosition {
SemBasicBlock origBlock;
SemBasicBlock phiBlock;
SemSsaReadPositionPhiInputEdge() { Specific::phiInputEdge(this, origBlock, phiBlock) }
predicate phiInput(SemSsaPhiNode phi, SemSsaVariable inp) { Specific::phiInput(this, phi, inp) }
SemBasicBlock getOrigBlock() { result = origBlock }
SemBasicBlock getPhiBlock() { result = phiBlock }
}
class SemSsaReadPositionBlock extends SemSsaReadPosition {
SemBasicBlock block;
SemSsaReadPositionBlock() { Specific::readBlock(this, block) }
SemBasicBlock getBlock() { result = block }
SemExpr getAnExpr() { result = getBlock().getAnExpr() }
}
/**
* Holds if `inp` is an input to `phi` along a back edge.
*/
predicate semBackEdge(SemSsaPhiNode phi, SemSsaVariable inp, SemSsaReadPositionPhiInputEdge edge) {
edge.phiInput(phi, inp) and
// Conservatively assume that every edge is a back edge if we don't have dominance information.
(
phi.getBasicBlock().bbDominates(edge.getOrigBlock()) or
not edge.getOrigBlock().hasDominanceInformation()
)
}

View File

@@ -1,301 +0,0 @@
/**
* Minimal, language-neutral type system for semantic analysis.
*/
private import SemanticTypeSpecific as Specific
class LanguageType = Specific::Type;
cached
private newtype TSemType =
TSemVoidType() { Specific::voidType(_) } or
TSemUnknownType() { Specific::unknownType(_) } or
TSemErrorType() { Specific::errorType(_) } or
TSemBooleanType(int byteSize) { Specific::booleanType(_, byteSize) } or
TSemIntegerType(int byteSize, boolean signed) { Specific::integerType(_, byteSize, signed) } or
TSemFloatingPointType(int byteSize) { Specific::floatingPointType(_, byteSize) } or
TSemAddressType(int byteSize) { Specific::addressType(_, byteSize) } or
TSemFunctionAddressType(int byteSize) { Specific::functionAddressType(_, byteSize) } or
TSemOpaqueType(int byteSize, Specific::OpaqueTypeTag tag) {
Specific::opaqueType(_, byteSize, tag)
}
/**
* The language-neutral type of a semantic expression,
* The interface to `SemType` and its subclasses is the same across all languages for which the IR
* is supported, so analyses that expect to be used for multiple languages should generally use
* `SemType` rather than a language-specific type.
*
* Many types from the language-specific type system will map to a single canonical `SemType`. Two
* types that map to the same `SemType` are considered equivalent by semantic analysis. As an
* example, in C++, all pointer types map to the same instance of `SemAddressType`.
*/
class SemType extends TSemType {
/** Gets a textual representation of this type. */
string toString() { none() }
/**
* Gets a string that uniquely identifies this `SemType`. This string is often the same as the
* result of `SemType.toString()`, but for some types it may be more verbose to ensure uniqueness.
*/
string getIdentityString() { result = toString() }
/**
* Gets the size of the type, in bytes, if known.
*
* This will hold for all `SemType` objects except `SemUnknownType` and `SemErrorType`.
*/
// This predicate is overridden with `pragma[noinline]` in every leaf subclass.
// This allows callers to ask for things like _the_ floating-point type of
// size 4 without getting a join that first finds all types of size 4 and
// _then_ restricts them to floating-point types.
int getByteSize() { none() }
}
/**
* An unknown type. Generally used to represent results and operands that access an unknown set of
* memory locations, such as the side effects of a function call.
*/
class SemUnknownType extends SemType, TSemUnknownType {
final override string toString() { result = "unknown" }
final override int getByteSize() { none() }
}
/**
* A void type, which has no values. Used to represent the result type of an expression that does
* not produce a result.
*/
class SemVoidType extends SemType, TSemVoidType {
final override string toString() { result = "void" }
final override int getByteSize() { result = 0 }
}
/**
* An error type. Used when an error in the source code prevents the extractor from determining the
* proper type.
*/
class SemErrorType extends SemType, TSemErrorType {
final override string toString() { result = "error" }
final override int getByteSize() { result = 0 }
}
private class SemSizedType extends SemType {
int byteSize;
SemSizedType() {
this = TSemBooleanType(byteSize) or
this = TSemIntegerType(byteSize, _) or
this = TSemFloatingPointType(byteSize) or
this = TSemAddressType(byteSize) or
this = TSemFunctionAddressType(byteSize) or
this = TSemOpaqueType(byteSize, _)
}
// Don't override `getByteSize()` here. The optimizer seems to generate better code when this is
// overridden only in the leaf classes.
}
/**
* A Boolean type, which can hold the values `true` (non-zero) or `false` (zero).
*/
class SemBooleanType extends SemSizedType, TSemBooleanType {
final override string toString() { result = "bool" + byteSize.toString() }
pragma[noinline]
final override int getByteSize() { result = byteSize }
}
/**
* A numeric type. This includes `SemSignedIntegerType`, `SemUnsignedIntegerType`, and
* `SemFloatingPointType`.
*/
class SemNumericType extends SemSizedType {
SemNumericType() {
this = TSemIntegerType(byteSize, _) or
this = TSemFloatingPointType(byteSize)
}
// Don't override `getByteSize()` here. The optimizer seems to generate better code when this is
// overridden only in the leaf classes.
}
/**
* An integer type. This includes `SemSignedIntegerType` and `SemUnsignedIntegerType`.
*/
class SemIntegerType extends SemNumericType {
boolean signed;
SemIntegerType() { this = TSemIntegerType(byteSize, signed) }
/** Holds if this integer type is signed. */
final predicate isSigned() { signed = true }
/** Holds if this integer type is unsigned. */
final predicate isUnsigned() { not isSigned() }
// Don't override `getByteSize()` here. The optimizer seems to generate better code when this is
// overridden only in the leaf classes.
}
/**
* A signed two's-complement integer. Also used to represent enums whose underlying type is a signed
* integer, as well as character types whose representation is signed.
*/
class SemSignedIntegerType extends SemIntegerType {
SemSignedIntegerType() { signed = true }
final override string toString() { result = "int" + byteSize.toString() }
pragma[noinline]
final override int getByteSize() { result = byteSize }
}
/**
* An unsigned two's-complement integer. Also used to represent enums whose underlying type is an
* unsigned integer, as well as character types whose representation is unsigned.
*/
class SemUnsignedIntegerType extends SemIntegerType {
SemUnsignedIntegerType() { signed = false }
final override string toString() { result = "uint" + byteSize.toString() }
pragma[noinline]
final override int getByteSize() { result = byteSize }
}
/**
* A floating-point type.
*/
class SemFloatingPointType extends SemNumericType, TSemFloatingPointType {
final override string toString() { result = "float" + byteSize.toString() }
pragma[noinline]
final override int getByteSize() { result = byteSize }
}
/**
* An address type, representing the memory address of data. Used to represent pointers, references,
* and lvalues, include those that are garbage collected.
*
* The address of a function is represented by the separate `SemFunctionAddressType`.
*/
class SemAddressType extends SemSizedType, TSemAddressType {
final override string toString() { result = "addr" + byteSize.toString() }
pragma[noinline]
final override int getByteSize() { result = byteSize }
}
/**
* An address type, representing the memory address of code. Used to represent function pointers,
* function references, and the target of a direct function call.
*/
class SemFunctionAddressType extends SemSizedType, TSemFunctionAddressType {
final override string toString() { result = "func" + byteSize.toString() }
pragma[noinline]
final override int getByteSize() { result = byteSize }
}
/**
* A type with known size that does not fit any of the other kinds of type. Used to represent
* classes, structs, unions, fixed-size arrays, pointers-to-member, and more.
*/
class SemOpaqueType extends SemSizedType, TSemOpaqueType {
Specific::OpaqueTypeTag tag;
SemOpaqueType() { this = TSemOpaqueType(byteSize, tag) }
final override string toString() {
result = "opaque" + byteSize.toString() + "{" + tag.toString() + "}"
}
final override string getIdentityString() {
result = "opaque" + byteSize.toString() + "{" + Specific::getOpaqueTagIdentityString(tag) + "}"
}
/**
* Gets the "tag" that differentiates this type from other incompatible opaque types that have the
* same size.
*/
final Specific::OpaqueTypeTag getTag() { result = tag }
pragma[noinline]
final override int getByteSize() { result = byteSize }
}
cached
SemType getSemanticType(Specific::Type type) {
exists(int byteSize |
Specific::booleanType(type, byteSize) and result = TSemBooleanType(byteSize)
or
exists(boolean signed |
Specific::integerType(type, byteSize, signed) and
result = TSemIntegerType(byteSize, signed)
)
or
Specific::floatingPointType(type, byteSize) and result = TSemFloatingPointType(byteSize)
or
Specific::addressType(type, byteSize) and result = TSemAddressType(byteSize)
or
Specific::functionAddressType(type, byteSize) and result = TSemFunctionAddressType(byteSize)
or
exists(Specific::OpaqueTypeTag tag |
Specific::opaqueType(type, byteSize, tag) and result = TSemOpaqueType(byteSize, tag)
)
)
or
Specific::errorType(type) and result = TSemErrorType()
or
Specific::unknownType(type) and result = TSemUnknownType()
}
/**
* Holds if the conversion from `fromType` to `toType` can never overflow or underflow.
*/
predicate conversionCannotOverflow(SemNumericType fromType, SemNumericType toType) {
// Identity cast
fromType = toType
or
// Treat any cast to an FP type as safe. It can lose precision, but not overflow.
toType instanceof SemFloatingPointType and fromType = any(SemNumericType n)
or
exists(SemIntegerType fromInteger, SemIntegerType toInteger, int fromSize, int toSize |
fromInteger = fromType and
toInteger = toType and
fromSize = fromInteger.getByteSize() and
toSize = toInteger.getByteSize()
|
// Conversion to a larger type. Safe unless converting signed -> unsigned.
fromSize < toSize and
(
toInteger.isSigned()
or
not fromInteger.isSigned()
)
)
}
/**
* INTERNAL: Do not use.
* Query predicates used to check invariants that should hold for all `SemType` objects.
*/
module SemTypeConsistency {
/**
* Holds if the type has no result for `getSemanticType()`.
*/
query predicate missingSemType(Specific::Type type, string message) {
not exists(getSemanticType(type)) and
message = "`Type` does not have a corresponding `SemType`."
}
/**
* Holds if the type has more than one result for `getSemanticType()`.
*/
query predicate multipleSemTypes(Specific::Type type, string message) {
strictcount(getSemanticType(type)) > 1 and
message =
"`Type` " + type + " has multiple `SemType`s: " +
concat(getSemanticType(type).toString(), ", ")
}
}

View File

@@ -1,43 +0,0 @@
/**
* C++-specific implementation of the semantic type system.
*/
private import semmle.code.cpp.ir.IR as IR
private import cpp as Cpp
private import semmle.code.cpp.ir.internal.IRCppLanguage as Language
class Type = IR::IRType;
class OpaqueTypeTag = Language::OpaqueTypeTag;
predicate voidType(Type type) { type instanceof IR::IRVoidType }
predicate errorType(Type type) { type instanceof IR::IRErrorType }
predicate unknownType(Type type) { type instanceof IR::IRUnknownType }
predicate booleanType(Type type, int byteSize) { byteSize = type.(IR::IRBooleanType).getByteSize() }
predicate integerType(Type type, int byteSize, boolean signed) {
byteSize = type.(IR::IRSignedIntegerType).getByteSize() and signed = true
or
byteSize = type.(IR::IRUnsignedIntegerType).getByteSize() and signed = false
}
predicate floatingPointType(Type type, int byteSize) {
byteSize = type.(IR::IRFloatingPointType).getByteSize()
}
predicate addressType(Type type, int byteSize) { byteSize = type.(IR::IRAddressType).getByteSize() }
predicate functionAddressType(Type type, int byteSize) {
byteSize = type.(IR::IRFunctionAddressType).getByteSize()
}
predicate opaqueType(Type type, int byteSize, OpaqueTypeTag tag) {
exists(IR::IROpaqueType opaque | opaque = type |
byteSize = opaque.getByteSize() and tag = opaque.getTag()
)
}
predicate getOpaqueTagIdentityString = Language::getOpaqueTagIdentityString/1;

View File

@@ -1,31 +0,0 @@
/**
* Simple constant analysis using the Semantic interface.
*/
private import experimental.semmle.code.cpp.semantic.Semantic
private import ConstantAnalysisSpecific as Specific
/** An expression that always has the same integer value. */
pragma[nomagic]
private predicate constantIntegerExpr(SemExpr e, int val) {
// An integer literal
e.(SemIntegerLiteralExpr).getIntValue() = val
or
// Copy of another constant
exists(SemSsaExplicitUpdate v, SemExpr src |
e = v.getAUse() and
src = v.getSourceExpr() and
constantIntegerExpr(src, val)
)
or
// Language-specific enhancements
val = Specific::getIntConstantValue(e)
}
/** An expression that always has the same integer value. */
class SemConstantIntegerExpr extends SemExpr {
SemConstantIntegerExpr() { constantIntegerExpr(this, _) }
/** Gets the integer value of this expression. */
int getIntValue() { constantIntegerExpr(this, result) }
}

View File

@@ -1,10 +0,0 @@
/**
* C++-specific implementation of constant analysis.
*/
private import experimental.semmle.code.cpp.semantic.Semantic
/**
* Gets the constant integer value of the specified expression, if any.
*/
int getIntConstantValue(SemExpr expr) { none() }

View File

@@ -1,334 +0,0 @@
/**
* Provides inferences of the form: `e` equals `b + v` modulo `m` where `e` is
* an expression, `b` is a `Bound` (typically zero or the value of an SSA
* variable), and `v` is an integer in the range `[0 .. m-1]`.
*/
/*
* The main recursion has base cases in both `ssaModulus` (for guarded reads) and `semExprModulus`
* (for constant values). The most interesting recursive case is `phiModulusRankStep`, which
* handles phi inputs.
*/
private import ModulusAnalysisSpecific::Private
private import experimental.semmle.code.cpp.semantic.Semantic
private import ConstantAnalysis
private import RangeUtils
/**
* Holds if `e + delta` equals `v` at `pos`.
*/
private predicate valueFlowStepSsa(SemSsaVariable v, SemSsaReadPosition pos, SemExpr e, int delta) {
semSsaUpdateStep(v, e, delta) and pos.hasReadOfVar(v)
or
exists(SemGuard guard, boolean testIsTrue |
pos.hasReadOfVar(v) and
guard = semEqFlowCond(v, e, delta, true, testIsTrue) and
semGuardDirectlyControlsSsaRead(guard, pos, testIsTrue)
)
}
/**
* Holds if `add` is the addition of `larg` and `rarg`, neither of which are
* `ConstantIntegerExpr`s.
*/
private predicate nonConstAddition(SemExpr add, SemExpr larg, SemExpr rarg) {
exists(SemAddExpr a | a = add |
larg = a.getLeftOperand() and
rarg = a.getRightOperand()
) and
not larg instanceof SemConstantIntegerExpr and
not rarg instanceof SemConstantIntegerExpr
}
/**
* Holds if `sub` is the subtraction of `larg` and `rarg`, where `rarg` is not
* a `ConstantIntegerExpr`.
*/
private predicate nonConstSubtraction(SemExpr sub, SemExpr larg, SemExpr rarg) {
exists(SemSubExpr s | s = sub |
larg = s.getLeftOperand() and
rarg = s.getRightOperand()
) and
not rarg instanceof SemConstantIntegerExpr
}
/** Gets an expression that is the remainder modulo `mod` of `arg`. */
private SemExpr modExpr(SemExpr arg, int mod) {
exists(SemRemExpr rem |
result = rem and
arg = rem.getLeftOperand() and
rem.getRightOperand().(SemConstantIntegerExpr).getIntValue() = mod and
mod >= 2
)
or
exists(SemConstantIntegerExpr c |
mod = 2.pow([1 .. 30]) and
c.getIntValue() = mod - 1 and
result.(SemBitAndExpr).hasOperands(arg, c)
)
}
/**
* Gets a guard that tests whether `v` is congruent with `val` modulo `mod` on
* its `testIsTrue` branch.
*/
private SemGuard moduloCheck(SemSsaVariable v, int val, int mod, boolean testIsTrue) {
exists(SemExpr rem, SemConstantIntegerExpr c, int r, boolean polarity |
result.isEquality(rem, c, polarity) and
c.getIntValue() = r and
rem = modExpr(v.getAUse(), mod) and
(
testIsTrue = polarity and val = r
or
testIsTrue = polarity.booleanNot() and
mod = 2 and
val = 1 - r and
(r = 0 or r = 1)
)
)
}
/**
* Holds if a guard ensures that `v` at `pos` is congruent with `val` modulo `mod`.
*/
private predicate moduloGuardedRead(SemSsaVariable v, SemSsaReadPosition pos, int val, int mod) {
exists(SemGuard guard, boolean testIsTrue |
pos.hasReadOfVar(v) and
guard = moduloCheck(v, val, mod, testIsTrue) and
semGuardControlsSsaRead(guard, pos, testIsTrue)
)
}
/** Holds if `factor` is a power of 2 that divides `mask`. */
bindingset[mask]
private predicate andmaskFactor(int mask, int factor) {
mask % factor = 0 and
factor = 2.pow([1 .. 30])
}
/** Holds if `e` is evenly divisible by `factor`. */
private predicate evenlyDivisibleExpr(SemExpr e, int factor) {
exists(SemConstantIntegerExpr c, int k | k = c.getIntValue() |
e.(SemMulExpr).getAnOperand() = c and factor = k.abs() and factor >= 2
or
e.(SemShiftLeftExpr).getRightOperand() = c and factor = 2.pow(k) and k > 0
or
e.(SemBitAndExpr).getAnOperand() = c and factor = max(int f | andmaskFactor(k, f))
)
}
/**
* Holds if `rix` is the number of input edges to `phi`.
*/
private predicate maxPhiInputRank(SemSsaPhiNode phi, int rix) {
rix = max(int r | rankedPhiInput(phi, _, _, r))
}
/**
* Gets the remainder of `val` modulo `mod`.
*
* For `mod = 0` the result equals `val` and for `mod > 1` the result is within
* the range `[0 .. mod-1]`.
*/
bindingset[val, mod]
private int remainder(int val, int mod) {
mod = 0 and result = val
or
mod > 1 and result = ((val % mod) + mod) % mod
}
/**
* Holds if `inp` is an input to `phi` and equals `phi` modulo `mod` along `edge`.
*/
private predicate phiSelfModulus(
SemSsaPhiNode phi, SemSsaVariable inp, SemSsaReadPositionPhiInputEdge edge, int mod
) {
exists(SemSsaBound phibound, int v, int m |
edge.phiInput(phi, inp) and
phibound.getAVariable() = phi and
ssaModulus(inp, edge, phibound, v, m) and
mod = m.gcd(v) and
mod != 1
)
}
/**
* Holds if `b + val` modulo `mod` is a candidate congruence class for `phi`.
*/
private predicate phiModulusInit(SemSsaPhiNode phi, SemBound b, int val, int mod) {
exists(SemSsaVariable inp, SemSsaReadPositionPhiInputEdge edge |
edge.phiInput(phi, inp) and
ssaModulus(inp, edge, b, val, mod)
)
}
/**
* Holds if all inputs to `phi` numbered `1` to `rix` are equal to `b + val` modulo `mod`.
*/
pragma[nomagic]
private predicate phiModulusRankStep(SemSsaPhiNode phi, SemBound b, int val, int mod, int rix) {
/*
* base case. If any phi input is equal to `b + val` modulo `mod`, that's a potential congruence
* class for the phi node.
*/
rix = 0 and
phiModulusInit(phi, b, val, mod)
or
exists(SemSsaVariable inp, SemSsaReadPositionPhiInputEdge edge, int v1, int m1 |
mod != 1 and
val = remainder(v1, mod)
|
/*
* Recursive case. If `inp` = `b + v2` mod `m2`, we combine that with the preceding potential
* congruence class `b + v1` mod `m1`. The result will be the congruence class of `v1` modulo
* the greatest common denominator of `m1`, `m2`, and `v1 - v2`.
*/
exists(int v2, int m2 |
rankedPhiInput(pragma[only_bind_out](phi), inp, edge, rix) and
phiModulusRankStep(phi, b, v1, m1, rix - 1) and
ssaModulus(inp, edge, b, v2, m2) and
mod = m1.gcd(m2).gcd(v1 - v2)
)
or
/*
* Recursive case. If `inp` = `phi` mod `m2`, we combine that with the preceding potential
* congruence class `b + v1` mod `m1`. The result will be a congruence class modulo the greatest
* common denominator of `m1` and `m2`.
*/
exists(int m2 |
rankedPhiInput(phi, inp, edge, rix) and
phiModulusRankStep(phi, b, v1, m1, rix - 1) and
phiSelfModulus(phi, inp, edge, m2) and
mod = m1.gcd(m2)
)
)
}
/**
* Holds if `phi` is equal to `b + val` modulo `mod`.
*/
private predicate phiModulus(SemSsaPhiNode phi, SemBound b, int val, int mod) {
exists(int r |
maxPhiInputRank(phi, r) and
phiModulusRankStep(phi, b, val, mod, r)
)
}
/**
* Holds if `v` at `pos` is equal to `b + val` modulo `mod`.
*/
private predicate ssaModulus(SemSsaVariable v, SemSsaReadPosition pos, SemBound b, int val, int mod) {
phiModulus(v, b, val, mod) and pos.hasReadOfVar(v)
or
b.(SemSsaBound).getAVariable() = v and pos.hasReadOfVar(v) and val = 0 and mod = 0
or
exists(SemExpr e, int val0, int delta |
semExprModulus(e, b, val0, mod) and
valueFlowStepSsa(v, pos, e, delta) and
val = remainder(val0 + delta, mod)
)
or
moduloGuardedRead(v, pos, val, mod) and b instanceof SemZeroBound
}
/**
* Holds if `e` is equal to `b + val` modulo `mod`.
*
* There are two cases for the modulus:
* - `mod = 0`: The equality `e = b + val` is an ordinary equality.
* - `mod > 1`: `val` lies within the range `[0 .. mod-1]`.
*/
cached
predicate semExprModulus(SemExpr e, SemBound b, int val, int mod) {
not ignoreExprModulus(e) and
(
e = b.getExpr(val) and mod = 0
or
evenlyDivisibleExpr(e, mod) and
val = 0 and
b instanceof SemZeroBound
or
exists(SemSsaVariable v, SemSsaReadPositionBlock bb |
ssaModulus(v, bb, b, val, mod) and
e = v.getAUse() and
bb.getAnExpr() = e
)
or
exists(SemExpr mid, int val0, int delta |
semExprModulus(mid, b, val0, mod) and
semValueFlowStep(e, mid, delta) and
val = remainder(val0 + delta, mod)
)
or
exists(SemConditionalExpr cond, int v1, int v2, int m1, int m2 |
cond = e and
condExprBranchModulus(cond, true, b, v1, m1) and
condExprBranchModulus(cond, false, b, v2, m2) and
mod = m1.gcd(m2).gcd(v1 - v2) and
mod != 1 and
val = remainder(v1, mod)
)
or
exists(SemBound b1, SemBound b2, int v1, int v2, int m1, int m2 |
addModulus(e, true, b1, v1, m1) and
addModulus(e, false, b2, v2, m2) and
mod = m1.gcd(m2) and
mod != 1 and
val = remainder(v1 + v2, mod)
|
b = b1 and b2 instanceof SemZeroBound
or
b = b2 and b1 instanceof SemZeroBound
)
or
exists(int v1, int v2, int m1, int m2 |
subModulus(e, true, b, v1, m1) and
subModulus(e, false, any(SemZeroBound zb), v2, m2) and
mod = m1.gcd(m2) and
mod != 1 and
val = remainder(v1 - v2, mod)
)
)
}
private predicate condExprBranchModulus(
SemConditionalExpr cond, boolean branch, SemBound b, int val, int mod
) {
semExprModulus(cond.getBranchExpr(branch), b, val, mod)
}
private predicate addModulus(SemExpr add, boolean isLeft, SemBound b, int val, int mod) {
exists(SemExpr larg, SemExpr rarg | nonConstAddition(add, larg, rarg) |
semExprModulus(larg, b, val, mod) and isLeft = true
or
semExprModulus(rarg, b, val, mod) and isLeft = false
)
}
private predicate subModulus(SemExpr sub, boolean isLeft, SemBound b, int val, int mod) {
exists(SemExpr larg, SemExpr rarg | nonConstSubtraction(sub, larg, rarg) |
semExprModulus(larg, b, val, mod) and isLeft = true
or
semExprModulus(rarg, b, val, mod) and isLeft = false
)
}
/**
* Holds if `inp` is an input to `phi` along `edge` and this input has index `r`
* in an arbitrary 1-based numbering of the input edges to `phi`.
*/
private predicate rankedPhiInput(
SemSsaPhiNode phi, SemSsaVariable inp, SemSsaReadPositionPhiInputEdge edge, int r
) {
edge.phiInput(phi, inp) and
edge =
rank[r](SemSsaReadPositionPhiInputEdge e |
e.phiInput(phi, _)
|
e order by e.getOrigBlock().getUniqueId()
)
}

View File

@@ -1,8 +0,0 @@
/**
* C++-specific implementation of modulus analysis.
*/
module Private {
private import experimental.semmle.code.cpp.semantic.Semantic
predicate ignoreExprModulus(SemExpr e) { none() }
}

View File

@@ -1,832 +0,0 @@
/**
* Provides classes and predicates for range analysis.
*
* An inferred bound can either be a specific integer, the abstract value of an
* SSA variable, or the abstract value of an interesting expression. The latter
* category includes array lengths that are not SSA variables.
*
* If an inferred bound relies directly on a condition, then this condition is
* reported as the reason for the bound.
*/
/*
* This library tackles range analysis as a flow problem. Consider e.g.:
* ```
* len = arr.length;
* if (x < len) { ... y = x-1; ... y ... }
* ```
* In this case we would like to infer `y <= arr.length - 2`, and this is
* accomplished by tracking the bound through a sequence of steps:
* ```
* arr.length --> len = .. --> x < len --> x-1 --> y = .. --> y
* ```
*
* In its simplest form the step relation `E1 --> E2` relates two expressions
* such that `E1 <= B` implies `E2 <= B` for any `B` (with a second separate
* step relation handling lower bounds). Examples of such steps include
* assignments `E2 = E1` and conditions `x <= E1` where `E2` is a use of `x`
* guarded by the condition.
*
* In order to handle subtractions and additions with constants, and strict
* comparisons, the step relation is augmented with an integer delta. With this
* generalization `E1 --(delta)--> E2` relates two expressions and an integer
* such that `E1 <= B` implies `E2 <= B + delta` for any `B`. This corresponds
* to the predicate `boundFlowStep`.
*
* The complete range analysis is then implemented as the transitive closure of
* the step relation summing the deltas along the way. If `E1` transitively
* steps to `E2`, `delta` is the sum of deltas along the path, and `B` is an
* interesting bound equal to the value of `E1` then `E2 <= B + delta`. This
* corresponds to the predicate `bounded`.
*
* Phi nodes need a little bit of extra handling. Consider `x0 = phi(x1, x2)`.
* There are essentially two cases:
* - If `x1 <= B + d1` and `x2 <= B + d2` then `x0 <= B + max(d1,d2)`.
* - If `x1 <= B + d1` and `x2 <= x0 + d2` with `d2 <= 0` then `x0 <= B + d1`.
* The first case is for whenever a bound can be proven without taking looping
* into account. The second case is relevant when `x2` comes from a back-edge
* where we can prove that the variable has been non-increasing through the
* loop-iteration as this means that any upper bound that holds prior to the
* loop also holds for the variable during the loop.
* This generalizes to a phi node with `n` inputs, so if
* `x0 = phi(x1, ..., xn)` and `xi <= B + delta` for one of the inputs, then we
* also have `x0 <= B + delta` if we can prove either:
* - `xj <= B + d` with `d <= delta` or
* - `xj <= x0 + d` with `d <= 0`
* for each input `xj`.
*
* As all inferred bounds can be related directly to a path in the source code
* the only source of non-termination is if successive redundant (and thereby
* increasingly worse) bounds are calculated along a loop in the source code.
* We prevent this by weakening the bound to a small finite set of bounds when
* a path follows a second back-edge (we postpone weakening till the second
* back-edge as a precise bound might require traversing a loop once).
*/
private import RangeAnalysisSpecific as Specific
private import RangeUtils
private import SignAnalysisCommon
private import ModulusAnalysis
private import experimental.semmle.code.cpp.semantic.Semantic
private import ConstantAnalysis
cached
private module RangeAnalysisCache {
cached
module RangeAnalysisPublic {
/**
* Holds if `b + delta` is a valid bound for `e`.
* - `upper = true` : `e <= b + delta`
* - `upper = false` : `e >= b + delta`
*
* The reason for the bound is given by `reason` and may be either a condition
* or `NoReason` if the bound was proven directly without the use of a bounding
* condition.
*/
cached
predicate semBounded(SemExpr e, SemBound b, int delta, boolean upper, SemReason reason) {
bounded(e, b, delta, upper, _, _, reason) and
bestBound(e, b, delta, upper)
}
}
/**
* Holds if `guard = boundFlowCond(_, _, _, _, _) or guard = eqFlowCond(_, _, _, _, _)`.
*/
cached
predicate possibleReason(SemGuard guard) {
guard = boundFlowCond(_, _, _, _, _) or guard = semEqFlowCond(_, _, _, _, _)
}
}
private import RangeAnalysisCache
import RangeAnalysisPublic
/**
* Holds if `b + delta` is a valid bound for `e` and this is the best such delta.
* - `upper = true` : `e <= b + delta`
* - `upper = false` : `e >= b + delta`
*/
private predicate bestBound(SemExpr e, SemBound b, int delta, boolean upper) {
delta = min(int d | bounded(e, b, d, upper, _, _, _)) and upper = true
or
delta = max(int d | bounded(e, b, d, upper, _, _, _)) and upper = false
}
/**
* Holds if `comp` corresponds to:
* - `upper = true` : `v <= e + delta` or `v < e + delta`
* - `upper = false` : `v >= e + delta` or `v > e + delta`
*/
private predicate boundCondition(
SemRelationalExpr comp, SemSsaVariable v, SemExpr e, int delta, boolean upper
) {
comp.getLesserOperand() = semSsaRead(v, delta) and e = comp.getGreaterOperand() and upper = true
or
comp.getGreaterOperand() = semSsaRead(v, delta) and e = comp.getLesserOperand() and upper = false
or
exists(SemSubExpr sub, SemConstantIntegerExpr c, int d |
// (v - d) - e < c
comp.getLesserOperand() = sub and
comp.getGreaterOperand() = c and
sub.getLeftOperand() = semSsaRead(v, d) and
sub.getRightOperand() = e and
upper = true and
delta = d + c.getIntValue()
or
// (v - d) - e > c
comp.getGreaterOperand() = sub and
comp.getLesserOperand() = c and
sub.getLeftOperand() = semSsaRead(v, d) and
sub.getRightOperand() = e and
upper = false and
delta = d + c.getIntValue()
or
// e - (v - d) < c
comp.getLesserOperand() = sub and
comp.getGreaterOperand() = c and
sub.getLeftOperand() = e and
sub.getRightOperand() = semSsaRead(v, d) and
upper = false and
delta = d - c.getIntValue()
or
// e - (v - d) > c
comp.getGreaterOperand() = sub and
comp.getLesserOperand() = c and
sub.getLeftOperand() = e and
sub.getRightOperand() = semSsaRead(v, d) and
upper = true and
delta = d - c.getIntValue()
)
}
/**
* Holds if `comp` is a comparison between `x` and `y` for which `y - x` has a
* fixed value modulo some `mod > 1`, such that the comparison can be
* strengthened by `strengthen` when evaluating to `testIsTrue`.
*/
private predicate modulusComparison(SemRelationalExpr comp, boolean testIsTrue, int strengthen) {
exists(
SemBound b, int v1, int v2, int mod1, int mod2, int mod, boolean resultIsStrict, int d, int k
|
// If `x <= y` and `x =(mod) b + v1` and `y =(mod) b + v2` then
// `0 <= y - x =(mod) v2 - v1`. By choosing `k =(mod) v2 - v1` with
// `0 <= k < mod` we get `k <= y - x`. If the resulting comparison is
// strict then the strengthening amount is instead `k - 1` modulo `mod`:
// `x < y` means `0 <= y - x - 1 =(mod) k - 1` so `k - 1 <= y - x - 1` and
// thus `k - 1 < y - x` with `0 <= k - 1 < mod`.
semExprModulus(comp.getLesserOperand(), b, v1, mod1) and
semExprModulus(comp.getGreaterOperand(), b, v2, mod2) and
mod = mod1.gcd(mod2) and
mod != 1 and
(testIsTrue = true or testIsTrue = false) and
(
if comp.isStrict()
then resultIsStrict = testIsTrue
else resultIsStrict = testIsTrue.booleanNot()
) and
(
resultIsStrict = true and d = 1
or
resultIsStrict = false and d = 0
) and
(
testIsTrue = true and k = v2 - v1
or
testIsTrue = false and k = v1 - v2
) and
strengthen = (((k - d) % mod) + mod) % mod
)
}
/**
* Gets a condition that tests whether `v` is bounded by `e + delta`.
*
* If the condition evaluates to `testIsTrue`:
* - `upper = true` : `v <= e + delta`
* - `upper = false` : `v >= e + delta`
*/
private SemGuard boundFlowCond(
SemSsaVariable v, SemExpr e, int delta, boolean upper, boolean testIsTrue
) {
exists(
SemRelationalExpr comp, int d1, int d2, int d3, int strengthen, boolean compIsUpper,
boolean resultIsStrict
|
comp = result.asExpr() and
boundCondition(comp, v, e, d1, compIsUpper) and
(testIsTrue = true or testIsTrue = false) and
upper = compIsUpper.booleanXor(testIsTrue.booleanNot()) and
(
if comp.isStrict()
then resultIsStrict = testIsTrue
else resultIsStrict = testIsTrue.booleanNot()
) and
(
if
getTrackedTypeForSsaVariable(v) instanceof SemIntegerType or
getTrackedTypeForSsaVariable(v) instanceof SemAddressType
then
upper = true and strengthen = -1
or
upper = false and strengthen = 1
else strengthen = 0
) and
(
exists(int k | modulusComparison(comp, testIsTrue, k) and d2 = strengthen * k)
or
not modulusComparison(comp, testIsTrue, _) and d2 = 0
) and
// A strict inequality `x < y` can be strengthened to `x <= y - 1`.
(
resultIsStrict = true and d3 = strengthen
or
resultIsStrict = false and d3 = 0
) and
delta = d1 + d2 + d3
)
or
exists(boolean testIsTrue0 |
semImplies_v2(result, testIsTrue, boundFlowCond(v, e, delta, upper, testIsTrue0), testIsTrue0)
)
or
result = semEqFlowCond(v, e, delta, true, testIsTrue) and
(upper = true or upper = false)
or
// guard that tests whether `v2` is bounded by `e + delta + d1 - d2` and
// exists a guard `guardEq` such that `v = v2 - d1 + d2`.
exists(SemSsaVariable v2, SemGuard guardEq, boolean eqIsTrue, int d1, int d2 |
guardEq = semEqFlowCond(v, semSsaRead(v2, d1), d2, true, eqIsTrue) and
result = boundFlowCond(v2, e, delta + d1 - d2, upper, testIsTrue) and
// guardEq needs to control guard
guardEq.directlyControls(result.getBasicBlock(), eqIsTrue)
)
}
private newtype TSemReason =
TSemNoReason() or
TSemCondReason(SemGuard guard) { possibleReason(guard) }
/**
* A reason for an inferred bound. This can either be `CondReason` if the bound
* is due to a specific condition, or `NoReason` if the bound is inferred
* without going through a bounding condition.
*/
abstract class SemReason extends TSemReason {
/** Gets a textual representation of this reason. */
abstract string toString();
}
/**
* A reason for an inferred bound that indicates that the bound is inferred
* without going through a bounding condition.
*/
class SemNoReason extends SemReason, TSemNoReason {
override string toString() { result = "NoReason" }
}
/** A reason for an inferred bound pointing to a condition. */
class SemCondReason extends SemReason, TSemCondReason {
/** Gets the condition that is the reason for the bound. */
SemGuard getCond() { this = TSemCondReason(result) }
override string toString() { result = getCond().toString() }
}
/**
* Holds if `e + delta` is a valid bound for `v` at `pos`.
* - `upper = true` : `v <= e + delta`
* - `upper = false` : `v >= e + delta`
*/
private predicate boundFlowStepSsa(
SemSsaVariable v, SemSsaReadPosition pos, SemExpr e, int delta, boolean upper, SemReason reason
) {
semSsaUpdateStep(v, e, delta) and
pos.hasReadOfVar(v) and
(upper = true or upper = false) and
reason = TSemNoReason()
or
exists(SemGuard guard, boolean testIsTrue |
pos.hasReadOfVar(v) and
guard = boundFlowCond(v, e, delta, upper, testIsTrue) and
semGuardDirectlyControlsSsaRead(guard, pos, testIsTrue) and
reason = TSemCondReason(guard)
)
}
/** Holds if `v != e + delta` at `pos` and `v` is of integral type. */
private predicate unequalFlowStepIntegralSsa(
SemSsaVariable v, SemSsaReadPosition pos, SemExpr e, int delta, SemReason reason
) {
getTrackedTypeForSsaVariable(v) instanceof SemIntegerType and
exists(SemGuard guard, boolean testIsTrue |
pos.hasReadOfVar(v) and
guard = semEqFlowCond(v, e, delta, false, testIsTrue) and
semGuardDirectlyControlsSsaRead(guard, pos, testIsTrue) and
reason = TSemCondReason(guard)
)
}
/**
* An expression that does conversion, boxing, or unboxing
*/
private class ConvertOrBoxExpr extends SemUnaryExpr {
ConvertOrBoxExpr() {
this instanceof SemConvertExpr
or
this instanceof SemBoxExpr
or
this instanceof SemUnboxExpr
}
}
/**
* A cast that can be ignored for the purpose of range analysis.
*/
private class SafeCastExpr extends ConvertOrBoxExpr {
SafeCastExpr() {
conversionCannotOverflow(getTrackedType(pragma[only_bind_into](getOperand())),
getTrackedType(this))
}
}
/**
* Holds if `typ` is a small integral type with the given lower and upper bounds.
*/
private predicate typeBound(SemIntegerType typ, int lowerbound, int upperbound) {
exists(int bitSize | bitSize = typ.getByteSize() * 8 |
bitSize < 32 and
(
if typ.isSigned()
then (
upperbound = 1.bitShiftLeft(bitSize - 1) - 1 and
lowerbound = -upperbound - 1
) else (
lowerbound = 0 and
upperbound = 1.bitShiftLeft(bitSize) - 1
)
)
)
}
/**
* A cast to a small integral type that may overflow or underflow.
*/
private class NarrowingCastExpr extends ConvertOrBoxExpr {
NarrowingCastExpr() {
not this instanceof SafeCastExpr and
typeBound(getTrackedType(this), _, _)
}
/** Gets the lower bound of the resulting type. */
int getLowerBound() { typeBound(getTrackedType(this), result, _) }
/** Gets the upper bound of the resulting type. */
int getUpperBound() { typeBound(getTrackedType(this), _, result) }
}
/** Holds if `e >= 1` as determined by sign analysis. */
private predicate strictlyPositiveIntegralExpr(SemExpr e) {
semStrictlyPositive(e) and getTrackedType(e) instanceof SemIntegerType
}
/** Holds if `e <= -1` as determined by sign analysis. */
private predicate strictlyNegativeIntegralExpr(SemExpr e) {
semStrictlyNegative(e) and getTrackedType(e) instanceof SemIntegerType
}
/**
* Holds if `e1 + delta` is a valid bound for `e2`.
* - `upper = true` : `e2 <= e1 + delta`
* - `upper = false` : `e2 >= e1 + delta`
*/
private predicate boundFlowStep(SemExpr e2, SemExpr e1, int delta, boolean upper) {
semValueFlowStep(e2, e1, delta) and
(upper = true or upper = false)
or
e2.(SafeCastExpr).getOperand() = e1 and
delta = 0 and
(upper = true or upper = false)
or
exists(SemExpr x | e2.(SemAddExpr).hasOperands(e1, x) |
// `x instanceof ConstantIntegerExpr` is covered by valueFlowStep
not x instanceof SemConstantIntegerExpr and
not e1 instanceof SemConstantIntegerExpr and
if strictlyPositiveIntegralExpr(x)
then upper = false and delta = 1
else
if semPositive(x)
then upper = false and delta = 0
else
if strictlyNegativeIntegralExpr(x)
then upper = true and delta = -1
else
if semNegative(x)
then upper = true and delta = 0
else none()
)
or
exists(SemExpr x, SemSubExpr sub |
e2 = sub and
sub.getLeftOperand() = e1 and
sub.getRightOperand() = x
|
// `x instanceof ConstantIntegerExpr` is covered by valueFlowStep
not x instanceof SemConstantIntegerExpr and
if strictlyPositiveIntegralExpr(x)
then upper = true and delta = -1
else
if semPositive(x)
then upper = true and delta = 0
else
if strictlyNegativeIntegralExpr(x)
then upper = false and delta = 1
else
if semNegative(x)
then upper = false and delta = 0
else none()
)
or
e2.(SemRemExpr).getRightOperand() = e1 and
semPositive(e1) and
delta = -1 and
upper = true
or
e2.(SemRemExpr).getLeftOperand() = e1 and semPositive(e1) and delta = 0 and upper = true
or
e2.(SemBitAndExpr).getAnOperand() = e1 and
semPositive(e1) and
delta = 0 and
upper = true
or
e2.(SemBitOrExpr).getAnOperand() = e1 and
semPositive(e2) and
delta = 0 and
upper = false
or
Specific::hasBound(e2, e1, delta, upper)
}
/** Holds if `e2 = e1 * factor` and `factor > 0`. */
private predicate boundFlowStepMul(SemExpr e2, SemExpr e1, int factor) {
exists(SemConstantIntegerExpr c, int k | k = c.getIntValue() and k > 0 |
e2.(SemMulExpr).hasOperands(e1, c) and factor = k
or
exists(SemShiftLeftExpr e |
e = e2 and e.getLeftOperand() = e1 and e.getRightOperand() = c and factor = 2.pow(k)
)
)
}
/**
* Holds if `e2 = e1 / factor` and `factor > 0`.
*
* This conflates division, right shift, and unsigned right shift and is
* therefore only valid for non-negative numbers.
*/
private predicate boundFlowStepDiv(SemExpr e2, SemExpr e1, int factor) {
exists(SemConstantIntegerExpr c, int k | k = c.getIntValue() and k > 0 |
exists(SemDivExpr e |
e = e2 and e.getLeftOperand() = e1 and e.getRightOperand() = c and factor = k
)
or
exists(SemShiftRightExpr e |
e = e2 and e.getLeftOperand() = e1 and e.getRightOperand() = c and factor = 2.pow(k)
)
or
exists(SemShiftRightUnsignedExpr e |
e = e2 and e.getLeftOperand() = e1 and e.getRightOperand() = c and factor = 2.pow(k)
)
)
}
/**
* Holds if `b + delta` is a valid bound for `v` at `pos`.
* - `upper = true` : `v <= b + delta`
* - `upper = false` : `v >= b + delta`
*/
private predicate boundedSsa(
SemSsaVariable v, SemSsaReadPosition pos, SemBound b, int delta, boolean upper,
boolean fromBackEdge, int origdelta, SemReason reason
) {
exists(SemExpr mid, int d1, int d2, SemReason r1, SemReason r2 |
boundFlowStepSsa(v, pos, mid, d1, upper, r1) and
bounded(mid, b, d2, upper, fromBackEdge, origdelta, r2) and
// upper = true: v <= mid + d1 <= b + d1 + d2 = b + delta
// upper = false: v >= mid + d1 >= b + d1 + d2 = b + delta
delta = d1 + d2 and
(if r1 instanceof SemNoReason then reason = r2 else reason = r1)
)
or
exists(int d, SemReason r1, SemReason r2 |
boundedSsa(v, pos, b, d, upper, fromBackEdge, origdelta, r2) or
boundedPhi(v, b, d, upper, fromBackEdge, origdelta, r2)
|
unequalIntegralSsa(v, pos, b, d, r1) and
(
upper = true and delta = d - 1
or
upper = false and delta = d + 1
) and
(
reason = r1
or
reason = r2 and not r2 instanceof SemNoReason
)
)
}
/**
* Holds if `v != b + delta` at `pos` and `v` is of integral type.
*/
private predicate unequalIntegralSsa(
SemSsaVariable v, SemSsaReadPosition pos, SemBound b, int delta, SemReason reason
) {
exists(SemExpr e, int d1, int d2 |
unequalFlowStepIntegralSsa(v, pos, e, d1, reason) and
boundedUpper(e, b, d1) and
boundedLower(e, b, d2) and
delta = d2 + d1
)
}
/**
* Holds if `b + delta` is an upper bound for `e`.
*
* This predicate only exists to prevent a bad standard order in `unequalIntegralSsa`.
*/
pragma[nomagic]
private predicate boundedUpper(SemExpr e, SemBound b, int delta) {
bounded(e, b, delta, true, _, _, _)
}
/**
* Holds if `b + delta` is a lower bound for `e`.
*
* This predicate only exists to prevent a bad standard order in `unequalIntegralSsa`.
*/
pragma[nomagic]
private predicate boundedLower(SemExpr e, SemBound b, int delta) {
bounded(e, b, delta, false, _, _, _)
}
/** Weakens a delta to lie in the range `[-1..1]`. */
bindingset[delta, upper]
private int weakenDelta(boolean upper, int delta) {
delta in [-1 .. 1] and result = delta
or
upper = true and result = -1 and delta < -1
or
upper = false and result = 1 and delta > 1
}
/**
* Holds if `b + delta` is a valid bound for `inp` when used as an input to
* `phi` along `edge`.
* - `upper = true` : `inp <= b + delta`
* - `upper = false` : `inp >= b + delta`
*/
private predicate boundedPhiInp(
SemSsaPhiNode phi, SemSsaVariable inp, SemSsaReadPositionPhiInputEdge edge, SemBound b, int delta,
boolean upper, boolean fromBackEdge, int origdelta, SemReason reason
) {
edge.phiInput(phi, inp) and
exists(int d, boolean fromBackEdge0 |
boundedSsa(inp, edge, b, d, upper, fromBackEdge0, origdelta, reason)
or
boundedPhi(inp, b, d, upper, fromBackEdge0, origdelta, reason)
or
b.(SemSsaBound).getAVariable() = inp and
d = 0 and
(upper = true or upper = false) and
fromBackEdge0 = false and
origdelta = 0 and
reason = TSemNoReason()
|
if semBackEdge(phi, inp, edge)
then
fromBackEdge = true and
(
fromBackEdge0 = true and delta = weakenDelta(upper, d - origdelta) + origdelta
or
fromBackEdge0 = false and delta = d
)
else (
delta = d and fromBackEdge = fromBackEdge0
)
)
}
/**
* Holds if `b + delta` is a valid bound for `inp` when used as an input to
* `phi` along `edge`.
* - `upper = true` : `inp <= b + delta`
* - `upper = false` : `inp >= b + delta`
*
* Equivalent to `boundedPhiInp(phi, inp, edge, b, delta, upper, _, _, _)`.
*/
pragma[noinline]
private predicate boundedPhiInp1(
SemSsaPhiNode phi, SemBound b, boolean upper, SemSsaVariable inp,
SemSsaReadPositionPhiInputEdge edge, int delta
) {
boundedPhiInp(phi, inp, edge, b, delta, upper, _, _, _)
}
/**
* Holds if `phi` is a valid bound for `inp` when used as an input to `phi`
* along `edge`.
* - `upper = true` : `inp <= phi`
* - `upper = false` : `inp >= phi`
*/
private predicate selfBoundedPhiInp(
SemSsaPhiNode phi, SemSsaVariable inp, SemSsaReadPositionPhiInputEdge edge, boolean upper
) {
exists(int d, SemSsaBound phibound |
phibound.getAVariable() = phi and
boundedPhiInp(phi, inp, edge, phibound, d, upper, _, _, _) and
(
upper = true and d <= 0
or
upper = false and d >= 0
)
)
}
/**
* Holds if `b + delta` is a valid bound for some input, `inp`, to `phi`, and
* thus a candidate bound for `phi`.
* - `upper = true` : `inp <= b + delta`
* - `upper = false` : `inp >= b + delta`
*/
pragma[noinline]
private predicate boundedPhiCand(
SemSsaPhiNode phi, boolean upper, SemBound b, int delta, boolean fromBackEdge, int origdelta,
SemReason reason
) {
exists(SemSsaVariable inp, SemSsaReadPositionPhiInputEdge edge |
boundedPhiInp(phi, inp, edge, b, delta, upper, fromBackEdge, origdelta, reason)
)
}
/**
* Holds if the candidate bound `b + delta` for `phi` is valid for the phi input
* `inp` along `edge`.
*/
private predicate boundedPhiCandValidForEdge(
SemSsaPhiNode phi, SemBound b, int delta, boolean upper, boolean fromBackEdge, int origdelta,
SemReason reason, SemSsaVariable inp, SemSsaReadPositionPhiInputEdge edge
) {
boundedPhiCand(phi, upper, b, delta, fromBackEdge, origdelta, reason) and
(
exists(int d | boundedPhiInp1(phi, b, upper, inp, edge, d) | upper = true and d <= delta)
or
exists(int d | boundedPhiInp1(phi, b, upper, inp, edge, d) | upper = false and d >= delta)
or
selfBoundedPhiInp(phi, inp, edge, upper)
)
}
/**
* Holds if `b + delta` is a valid bound for `phi`.
* - `upper = true` : `phi <= b + delta`
* - `upper = false` : `phi >= b + delta`
*/
private predicate boundedPhi(
SemSsaPhiNode phi, SemBound b, int delta, boolean upper, boolean fromBackEdge, int origdelta,
SemReason reason
) {
forex(SemSsaVariable inp, SemSsaReadPositionPhiInputEdge edge | edge.phiInput(phi, inp) |
boundedPhiCandValidForEdge(phi, b, delta, upper, fromBackEdge, origdelta, reason, inp, edge)
)
}
/**
* Holds if `e` has an upper (for `upper = true`) or lower
* (for `upper = false`) bound of `b`.
*/
private predicate baseBound(SemExpr e, int b, boolean upper) {
Specific::hasConstantBound(e, b, upper)
or
upper = false and
b = 0 and
semPositive(e.(SemBitAndExpr).getAnOperand()) and
// REVIEW: We let the language opt out here to preserve original results.
not Specific::ignoreZeroLowerBound(e)
}
/**
* Holds if the value being cast has an upper (for `upper = true`) or lower
* (for `upper = false`) bound within the bounds of the resulting type.
* For `upper = true` this means that the cast will not overflow and for
* `upper = false` this means that the cast will not underflow.
*/
private predicate safeNarrowingCast(NarrowingCastExpr cast, boolean upper) {
exists(int bound | bounded(cast.getOperand(), any(SemZeroBound zb), bound, upper, _, _, _) |
upper = true and bound <= cast.getUpperBound()
or
upper = false and bound >= cast.getLowerBound()
)
}
pragma[noinline]
private predicate boundedCastExpr(
NarrowingCastExpr cast, SemBound b, int delta, boolean upper, boolean fromBackEdge, int origdelta,
SemReason reason
) {
bounded(cast.getOperand(), b, delta, upper, fromBackEdge, origdelta, reason)
}
/**
* Holds if `b + delta` is a valid bound for `e`.
* - `upper = true` : `e <= b + delta`
* - `upper = false` : `e >= b + delta`
*/
private predicate bounded(
SemExpr e, SemBound b, int delta, boolean upper, boolean fromBackEdge, int origdelta,
SemReason reason
) {
not Specific::ignoreExprBound(e) and
(
e = b.getExpr(delta) and
(upper = true or upper = false) and
fromBackEdge = false and
origdelta = delta and
reason = TSemNoReason()
or
baseBound(e, delta, upper) and
b instanceof SemZeroBound and
fromBackEdge = false and
origdelta = delta and
reason = TSemNoReason()
or
exists(SemSsaVariable v, SemSsaReadPositionBlock bb |
boundedSsa(v, bb, b, delta, upper, fromBackEdge, origdelta, reason) and
e = v.getAUse() and
bb.getBlock() = e.getBasicBlock()
)
or
exists(SemExpr mid, int d1, int d2 |
boundFlowStep(e, mid, d1, upper) and
// Constants have easy, base-case bounds, so let's not infer any recursive bounds.
not e instanceof SemConstantIntegerExpr and
bounded(mid, b, d2, upper, fromBackEdge, origdelta, reason) and
// upper = true: e <= mid + d1 <= b + d1 + d2 = b + delta
// upper = false: e >= mid + d1 >= b + d1 + d2 = b + delta
delta = d1 + d2
)
or
exists(SemSsaPhiNode phi |
boundedPhi(phi, b, delta, upper, fromBackEdge, origdelta, reason) and
e = phi.getAUse()
)
or
exists(SemExpr mid, int factor, int d |
boundFlowStepMul(e, mid, factor) and
not e instanceof SemConstantIntegerExpr and
bounded(mid, b, d, upper, fromBackEdge, origdelta, reason) and
b instanceof SemZeroBound and
delta = d * factor
)
or
exists(SemExpr mid, int factor, int d |
boundFlowStepDiv(e, mid, factor) and
not e instanceof SemConstantIntegerExpr and
bounded(mid, b, d, upper, fromBackEdge, origdelta, reason) and
b instanceof SemZeroBound and
d >= 0 and
delta = d / factor
)
or
exists(NarrowingCastExpr cast |
cast = e and
safeNarrowingCast(cast, upper.booleanNot()) and
boundedCastExpr(cast, b, delta, upper, fromBackEdge, origdelta, reason)
)
or
exists(
SemConditionalExpr cond, int d1, int d2, boolean fbe1, boolean fbe2, int od1, int od2,
SemReason r1, SemReason r2
|
cond = e and
boundedConditionalExpr(cond, b, upper, true, d1, fbe1, od1, r1) and
boundedConditionalExpr(cond, b, upper, false, d2, fbe2, od2, r2) and
(
delta = d1 and fromBackEdge = fbe1 and origdelta = od1 and reason = r1
or
delta = d2 and fromBackEdge = fbe2 and origdelta = od2 and reason = r2
)
|
upper = true and delta = d1.maximum(d2)
or
upper = false and delta = d1.minimum(d2)
)
)
}
private predicate boundedConditionalExpr(
SemConditionalExpr cond, SemBound b, boolean upper, boolean branch, int delta,
boolean fromBackEdge, int origdelta, SemReason reason
) {
bounded(cond.getBranchExpr(branch), b, delta, upper, fromBackEdge, origdelta, reason)
}

View File

@@ -1,88 +0,0 @@
/**
* C++-specific implementation of range analysis.
*/
private import experimental.semmle.code.cpp.semantic.Semantic
/**
* Holds if the specified expression should be excluded from the result of `ssaRead()`.
*
* This predicate is to keep the results identical to the original Java implementation. It should be
* removed once we have the new implementation matching the old results exactly.
*/
predicate ignoreSsaReadCopy(SemExpr e) { none() }
/**
* Ignore the bound on this expression.
*
* This predicate is to keep the results identical to the original Java implementation. It should be
* removed once we have the new implementation matching the old results exactly.
*/
predicate ignoreExprBound(SemExpr e) { none() }
/**
* Ignore any inferred zero lower bound on this expression.
*
* This predicate is to keep the results identical to the original Java implementation. It should be
* removed once we have the new implementation matching the old results exactly.
*/
predicate ignoreZeroLowerBound(SemExpr e) { none() }
/**
* Holds if the specified expression should be excluded from the result of `ssaRead()`.
*
* This predicate is to keep the results identical to the original Java implementation. It should be
* removed once we have the new implementation matching the old results exactly.
*/
predicate ignoreSsaReadArithmeticExpr(SemExpr e) { none() }
/**
* Holds if the specified variable should be excluded from the result of `ssaRead()`.
*
* This predicate is to keep the results identical to the original Java implementation. It should be
* removed once we have the new implementation matching the old results exactly.
*/
predicate ignoreSsaReadAssignment(SemSsaVariable v) { none() }
/**
* Adds additional results to `ssaRead()` that are specific to Java.
*
* This predicate handles propagation of offsets for post-increment and post-decrement expressions
* in exactly the same way as the old Java implementation. Once the new implementation matches the
* old one, we should remove this predicate and propagate deltas for all similar patterns, whether
* or not they come from a post-increment/decrement expression.
*/
SemExpr specificSsaRead(SemSsaVariable v, int delta) { none() }
/**
* Holds if `e >= bound` (if `upper = false`) or `e <= bound` (if `upper = true`).
*/
predicate hasConstantBound(SemExpr e, int bound, boolean upper) { none() }
/**
* Holds if `e >= bound + delta` (if `upper = false`) or `e <= bound + delta` (if `upper = true`).
*/
predicate hasBound(SemExpr e, SemExpr bound, int delta, boolean upper) { none() }
/**
* Holds if the value of `dest` is known to be `src + delta`.
*/
predicate additionalValueFlowStep(SemExpr dest, SemExpr src, int delta) { none() }
/**
* Gets the type that range analysis should use to track the result of the specified expression,
* if a type other than the original type of the expression is to be used.
*
* This predicate is commonly used in languages that support immutable "boxed" types that are
* actually references but whose values can be tracked as the type contained in the box.
*/
SemType getAlternateType(SemExpr e) { none() }
/**
* Gets the type that range analysis should use to track the result of the specified source
* variable, if a type other than the original type of the expression is to be used.
*
* This predicate is commonly used in languages that support immutable "boxed" types that are
* actually references but whose values can be tracked as the type contained in the box.
*/
SemType getAlternateTypeForSsaVariable(SemSsaVariable var) { none() }

View File

@@ -1,135 +0,0 @@
/**
* Provides utility predicates for range analysis.
*/
private import experimental.semmle.code.cpp.semantic.Semantic
private import RangeAnalysisSpecific as Specific
private import ConstantAnalysis
/**
* Gets an expression that equals `v - d`.
*/
SemExpr semSsaRead(SemSsaVariable v, int delta) {
// There are various language-specific extension points that can be removed once we no longer
// expect to match the original Java implementation's results exactly.
result = v.getAUse() and delta = 0
or
exists(int d1, SemConstantIntegerExpr c |
result.(SemAddExpr).hasOperands(semSsaRead(v, d1), c) and
delta = d1 - c.getIntValue() and
not Specific::ignoreSsaReadArithmeticExpr(result)
)
or
exists(SemSubExpr sub, int d1, SemConstantIntegerExpr c |
result = sub and
sub.getLeftOperand() = semSsaRead(v, d1) and
sub.getRightOperand() = c and
delta = d1 + c.getIntValue() and
not Specific::ignoreSsaReadArithmeticExpr(result)
)
or
result = v.(SemSsaExplicitUpdate).getSourceExpr() and
delta = 0 and
not Specific::ignoreSsaReadAssignment(v)
or
result = Specific::specificSsaRead(v, delta)
or
result.(SemCopyValueExpr).getOperand() = semSsaRead(v, delta) and
not Specific::ignoreSsaReadCopy(result)
or
result.(SemStoreExpr).getOperand() = semSsaRead(v, delta)
}
/**
* Gets a condition that tests whether `v` equals `e + delta`.
*
* If the condition evaluates to `testIsTrue`:
* - `isEq = true` : `v == e + delta`
* - `isEq = false` : `v != e + delta`
*/
SemGuard semEqFlowCond(SemSsaVariable v, SemExpr e, int delta, boolean isEq, boolean testIsTrue) {
exists(boolean eqpolarity |
result.isEquality(semSsaRead(v, delta), e, eqpolarity) and
(testIsTrue = true or testIsTrue = false) and
eqpolarity.booleanXor(testIsTrue).booleanNot() = isEq
)
or
exists(boolean testIsTrue0 |
semImplies_v2(result, testIsTrue, semEqFlowCond(v, e, delta, isEq, testIsTrue0), testIsTrue0)
)
}
/**
* Holds if `v` is an `SsaExplicitUpdate` that equals `e + delta`.
*/
predicate semSsaUpdateStep(SemSsaExplicitUpdate v, SemExpr e, int delta) {
exists(SemExpr defExpr | defExpr = v.getSourceExpr() |
defExpr.(SemCopyValueExpr).getOperand() = e and delta = 0
or
defExpr.(SemStoreExpr).getOperand() = e and delta = 0
or
defExpr.(SemAddOneExpr).getOperand() = e and delta = 1
or
defExpr.(SemSubOneExpr).getOperand() = e and delta = -1
or
e = defExpr and
not (
defExpr instanceof SemCopyValueExpr or
defExpr instanceof SemStoreExpr or
defExpr instanceof SemAddOneExpr or
defExpr instanceof SemSubOneExpr
) and
delta = 0
)
}
/**
* Holds if `e1 + delta` equals `e2`.
*/
predicate semValueFlowStep(SemExpr e2, SemExpr e1, int delta) {
e2.(SemCopyValueExpr).getOperand() = e1 and delta = 0
or
e2.(SemStoreExpr).getOperand() = e1 and delta = 0
or
e2.(SemAddOneExpr).getOperand() = e1 and delta = 1
or
e2.(SemSubOneExpr).getOperand() = e1 and delta = -1
or
Specific::additionalValueFlowStep(e2, e1, delta)
or
exists(SemExpr x | e2.(SemAddExpr).hasOperands(e1, x) |
x.(SemConstantIntegerExpr).getIntValue() = delta
)
or
exists(SemExpr x, SemSubExpr sub |
e2 = sub and
sub.getLeftOperand() = e1 and
sub.getRightOperand() = x
|
x.(SemConstantIntegerExpr).getIntValue() = -delta
)
}
/**
* Gets the type used to track the specified expression's range information.
*
* Usually, this just `e.getSemType()`, but the language can override this to track immutable boxed
* primitive types as the underlying primitive type.
*/
SemType getTrackedType(SemExpr e) {
result = Specific::getAlternateType(e)
or
not exists(Specific::getAlternateType(e)) and result = e.getSemType()
}
/**
* Gets the type used to track the specified source variable's range information.
*
* Usually, this just `e.getType()`, but the language can override this to track immutable boxed
* primitive types as the underlying primitive type.
*/
SemType getTrackedTypeForSsaVariable(SemSsaVariable var) {
result = Specific::getAlternateTypeForSsaVariable(var)
or
not exists(Specific::getAlternateTypeForSsaVariable(var)) and result = var.getType()
}

View File

@@ -1,267 +0,0 @@
private import experimental.semmle.code.cpp.semantic.Semantic
newtype TSign =
TNeg() or
TZero() or
TPos()
/** Class representing expression signs (+, -, 0). */
class Sign extends TSign {
/** Gets the string representation of this sign. */
string toString() {
result = "-" and this = TNeg()
or
result = "0" and this = TZero()
or
result = "+" and this = TPos()
}
/** Gets a possible sign after incrementing an expression that has this sign. */
Sign inc() {
this = TNeg() and result = TNeg()
or
this = TNeg() and result = TZero()
or
this = TZero() and result = TPos()
or
this = TPos() and result = TPos()
}
/** Gets a possible sign after decrementing an expression that has this sign. */
Sign dec() { result.inc() = this }
/** Gets a possible sign after negating an expression that has this sign. */
Sign neg() {
this = TNeg() and result = TPos()
or
this = TZero() and result = TZero()
or
this = TPos() and result = TNeg()
}
/**
* Gets a possible sign after bitwise complementing an expression that has this
* sign.
*/
Sign bitnot() {
this = TNeg() and result = TPos()
or
this = TNeg() and result = TZero()
or
this = TZero() and result = TNeg()
or
this = TPos() and result = TNeg()
}
/**
* Gets a possible sign after adding an expression with sign `s` to an expression
* that has this sign.
*/
Sign add(Sign s) {
this = TZero() and result = s
or
s = TZero() and result = this
or
this = s and this = result
or
this = TPos() and s = TNeg()
or
this = TNeg() and s = TPos()
}
/**
* Gets a possible sign after subtracting an expression with sign `s` from an expression
* that has this sign.
*/
Sign sub(Sign s) { result = add(s.neg()) }
/**
* Gets a possible sign after multiplying an expression with sign `s` to an expression
* that has this sign.
*/
Sign mul(Sign s) {
result = TZero() and this = TZero()
or
result = TZero() and s = TZero()
or
result = TNeg() and this = TPos() and s = TNeg()
or
result = TNeg() and this = TNeg() and s = TPos()
or
result = TPos() and this = TPos() and s = TPos()
or
result = TPos() and this = TNeg() and s = TNeg()
}
/**
* Gets a possible sign after integer dividing an expression that has this sign
* by an expression with sign `s`.
*/
Sign div(Sign s) {
result = TZero() and s = TNeg() // ex: 3 / -5 = 0
or
result = TZero() and s = TPos() // ex: 3 / 5 = 0
or
result = TNeg() and this = TPos() and s = TNeg()
or
result = TNeg() and this = TNeg() and s = TPos()
or
result = TPos() and this = TPos() and s = TPos()
or
result = TPos() and this = TNeg() and s = TNeg()
}
/**
* Gets a possible sign after modulo dividing an expression that has this sign
* by an expression with sign `s`.
*/
Sign rem(Sign s) {
result = TZero() and s = TNeg()
or
result = TZero() and s = TPos()
or
result = this and s = TNeg()
or
result = this and s = TPos()
}
/**
* Gets a possible sign after bitwise `and` of an expression that has this sign
* and an expression with sign `s`.
*/
Sign bitand(Sign s) {
result = TZero() and this = TZero()
or
result = TZero() and s = TZero()
or
result = TZero() and this = TPos()
or
result = TZero() and s = TPos()
or
result = TNeg() and this = TNeg() and s = TNeg()
or
result = TPos() and this = TNeg() and s = TPos()
or
result = TPos() and this = TPos() and s = TNeg()
or
result = TPos() and this = TPos() and s = TPos()
}
/**
* Gets a possible sign after bitwise `or` of an expression that has this sign
* and an expression with sign `s`.
*/
Sign bitor(Sign s) {
result = TZero() and this = TZero() and s = TZero()
or
result = TNeg() and this = TNeg()
or
result = TNeg() and s = TNeg()
or
result = TPos() and this = TPos() and s = TZero()
or
result = TPos() and this = TZero() and s = TPos()
or
result = TPos() and this = TPos() and s = TPos()
}
/**
* Gets a possible sign after bitwise `xor` of an expression that has this sign
* and an expression with sign `s`.
*/
Sign bitxor(Sign s) {
result = TZero() and this = s
or
result = this and s = TZero()
or
result = s and this = TZero()
or
result = TPos() and this = TPos() and s = TPos()
or
result = TNeg() and this = TNeg() and s = TPos()
or
result = TNeg() and this = TPos() and s = TNeg()
or
result = TPos() and this = TNeg() and s = TNeg()
}
/**
* Gets a possible sign after left shift of an expression that has this sign
* by an expression with sign `s`.
*/
Sign lshift(Sign s) {
result = TZero() and this = TZero()
or
result = this and s = TZero()
or
this != TZero() and s != TZero()
}
/**
* Gets a possible sign after right shift of an expression that has this sign
* by an expression with sign `s`.
*/
Sign rshift(Sign s) {
result = TZero() and this = TZero()
or
result = this and s = TZero()
or
result = TNeg() and this = TNeg()
or
result != TNeg() and this = TPos() and s != TZero()
}
/**
* Gets a possible sign after unsigned right shift of an expression that has
* this sign by an expression with sign `s`.
*/
Sign urshift(Sign s) {
result = TZero() and this = TZero()
or
result = this and s = TZero()
or
result != TZero() and this = TNeg() and s != TZero()
or
result != TNeg() and this = TPos() and s != TZero()
}
/** Perform `op` on this sign. */
Sign applyUnaryOp(Opcode op) {
op instanceof Opcode::CopyValue and result = this
or
op instanceof Opcode::Store and result = this
or
op instanceof Opcode::AddOne and result = inc()
or
op instanceof Opcode::SubOne and result = dec()
or
op instanceof Opcode::Negate and result = neg()
or
op instanceof Opcode::BitComplement and result = bitnot()
}
/** Perform `op` on this sign and sign `s`. */
Sign applyBinaryOp(Sign s, Opcode op) {
op instanceof Opcode::Add and result = add(s)
or
op instanceof Opcode::Sub and result = sub(s)
or
op instanceof Opcode::Mul and result = mul(s)
or
op instanceof Opcode::Div and result = div(s)
or
op instanceof Opcode::Rem and result = rem(s)
or
op instanceof Opcode::BitAnd and result = bitand(s)
or
op instanceof Opcode::BitOr and result = bitor(s)
or
op instanceof Opcode::BitXor and result = bitxor(s)
or
op instanceof Opcode::ShiftLeft and result = lshift(s)
or
op instanceof Opcode::ShiftRight and result = rshift(s)
or
op instanceof Opcode::ShiftRightUnsigned and result = urshift(s)
}
}

View File

@@ -1,501 +0,0 @@
/**
* Provides sign analysis to determine whether expression are always positive
* or negative.
*
* The analysis is implemented as an abstract interpretation over the
* three-valued domain `{negative, zero, positive}`.
*/
private import SignAnalysisSpecific as Specific
private import experimental.semmle.code.cpp.semantic.Semantic
private import ConstantAnalysis
private import RangeUtils
private import Sign
/**
* An SSA definition for which the analysis can compute the sign.
*
* The actual computation of the sign is done in an override of the `getSign()` predicate. The
* charpred of any subclass must _not_ invoke `getSign()`, directly or indirectly. This ensures
* that the charpred does not introduce negative recursion. The `getSign()` predicate may be
* recursive.
*/
abstract private class SignDef instanceof SemSsaVariable {
final string toString() { result = super.toString() }
/** Gets the possible signs of this SSA definition. */
abstract Sign getSign();
}
/** An SSA definition whose sign is computed based on standard flow. */
abstract private class FlowSignDef extends SignDef {
abstract override Sign getSign();
}
/** An SSA definition whose sign is determined by the sign of that definitions source expression. */
private class ExplicitSignDef extends FlowSignDef {
SemSsaExplicitUpdate update;
ExplicitSignDef() { update = this }
final override Sign getSign() { result = semExprSign(update.getSourceExpr()) }
}
/** An SSA Phi definition, whose sign is the union of the signs of its inputs. */
private class PhiSignDef extends FlowSignDef {
SemSsaPhiNode phi;
PhiSignDef() { phi = this }
final override Sign getSign() {
exists(SemSsaVariable inp, SemSsaReadPositionPhiInputEdge edge |
edge.phiInput(phi, inp) and
result = semSsaSign(inp, edge)
)
}
}
/** An SSA definition whose sign is computed by a language-specific implementation. */
abstract class CustomSignDef extends SignDef {
abstract override Sign getSign();
}
/**
* An expression for which the analysis can compute the sign.
*
* The actual computation of the sign is done in an override of the `getSign()` predicate. The
* charpred of any subclass must _not_ invoke `getSign()`, directly or indirectly. This ensures
* that the charpred does not introduce negative recursion. The `getSign()` predicate may be
* recursive.
*
* Concrete implementations extend one of the following subclasses:
* - `ConstantSignExpr`, for expressions with a compile-time constant value.
* - `FlowSignExpr`, for expressions whose sign can be computed from the signs of their operands.
* - `CustomsignExpr`, for expressions whose sign can be computed by a language-specific
* implementation.
*
* If the same expression matches more than one of the above subclasses, the sign is computed as
* follows:
* - The sign of a `ConstantSignExpr` is computed solely from `ConstantSignExpr.getSign()`,
* regardless of any other subclasses.
* - If a non-`ConstantSignExpr` expression matches exactly one of `FlowSignExpr` or
* `CustomSignExpr`, the sign is computed by that class' `getSign()` predicate.
* - If a non-`ConstantSignExpr` expression matches both `FlowSignExpr` and `CustomSignExpr`, the
* sign is the _intersection_ of the signs of those two classes' `getSign()` predicates. Thus,
* both classes have the opportunity to _restrict_ the set of possible signs, not to generate new
* possible signs.
* - If an expression does not match any of the three subclasses, then it can have any sign.
*
* Note that the `getSign()` predicate is introduced only in subclasses of `SignExpr`.
*/
abstract class SignExpr instanceof SemExpr {
SignExpr() { not Specific::ignoreExprSign(this) }
final string toString() { result = super.toString() }
abstract Sign getSign();
}
/** An expression whose sign is determined by its constant numeric value. */
private class ConstantSignExpr extends SignExpr {
ConstantSignExpr() {
this instanceof SemConstantIntegerExpr or
exists(this.(SemNumericLiteralExpr).getApproximateFloatValue())
}
final override Sign getSign() {
exists(int i | this.(SemConstantIntegerExpr).getIntValue() = i |
i < 0 and result = TNeg()
or
i = 0 and result = TZero()
or
i > 0 and result = TPos()
)
or
not exists(this.(SemConstantIntegerExpr).getIntValue()) and
exists(float f | f = this.(SemNumericLiteralExpr).getApproximateFloatValue() |
f < 0 and result = TNeg()
or
f = 0 and result = TZero()
or
f > 0 and result = TPos()
)
}
}
abstract private class NonConstantSignExpr extends SignExpr {
NonConstantSignExpr() { not this instanceof ConstantSignExpr }
final override Sign getSign() {
// The result is the _intersection_ of the signs computed from flow and by the language.
(result = this.(FlowSignExpr).getSignRestriction() or not this instanceof FlowSignExpr) and
(result = this.(CustomSignExpr).getSignRestriction() or not this instanceof CustomSignExpr)
}
}
/** An expression whose sign is computed from the signs of its operands. */
abstract private class FlowSignExpr extends NonConstantSignExpr {
abstract Sign getSignRestriction();
}
/** An expression whose sign is computed by a language-specific implementation. */
abstract class CustomSignExpr extends NonConstantSignExpr {
abstract Sign getSignRestriction();
}
/** An expression whose sign is unknown. */
private class UnknownSignExpr extends SignExpr {
UnknownSignExpr() {
not this instanceof FlowSignExpr and
not this instanceof CustomSignExpr and
not this instanceof ConstantSignExpr and
(
// Only track numeric types.
getTrackedType(this) instanceof SemNumericType
or
// Unless the language says to track this expression anyway.
Specific::trackUnknownNonNumericExpr(this)
)
}
final override Sign getSign() { semAnySign(result) }
}
/**
* A `Load` expression whose sign is computed from the sign of its SSA definition, restricted by
* inference from any intervening guards.
*/
class UseSignExpr extends FlowSignExpr {
SemSsaVariable v;
UseSignExpr() { v.getAUse() = this }
override Sign getSignRestriction() {
// Propagate via SSA
// Propagate the sign from the def of `v`, incorporating any inference from guards.
result = semSsaSign(v, any(SemSsaReadPositionBlock bb | bb.getAnExpr() = this))
or
// No block for this read. Just use the sign of the def.
// REVIEW: How can this happen?
not exists(SemSsaReadPositionBlock bb | bb.getAnExpr() = this) and
result = semSsaDefSign(v)
}
}
/** A binary expression whose sign is computed from the signs of its operands. */
private class BinarySignExpr extends FlowSignExpr {
SemBinaryExpr binary;
BinarySignExpr() { binary = this }
override Sign getSignRestriction() {
exists(SemExpr left, SemExpr right |
binaryExprOperands(binary, left, right) and
result =
semExprSign(pragma[only_bind_out](left))
.applyBinaryOp(semExprSign(pragma[only_bind_out](right)), binary.getOpcode())
)
or
exists(SemDivExpr div | div = binary |
result = semExprSign(div.getLeftOperand()) and
result != TZero() and
div.getRightOperand().(SemFloatingPointLiteralExpr).getFloatValue() = 0
)
}
}
pragma[nomagic]
private predicate binaryExprOperands(SemBinaryExpr binary, SemExpr left, SemExpr right) {
binary.getLeftOperand() = left and binary.getRightOperand() = right
}
/**
* A `Convert`, `Box`, or `Unbox` expression.
*/
private class SemCastExpr extends SemUnaryExpr {
SemCastExpr() {
this instanceof SemConvertExpr
or
this instanceof SemBoxExpr
or
this instanceof SemUnboxExpr
}
}
/** A unary expression whose sign is computed from the sign of its operand. */
private class UnarySignExpr extends FlowSignExpr {
SemUnaryExpr unary;
UnarySignExpr() { unary = this and not this instanceof SemCastExpr }
override Sign getSignRestriction() {
result = semExprSign(pragma[only_bind_out](unary.getOperand())).applyUnaryOp(unary.getOpcode())
}
}
/**
* A `Convert`, `Box`, or `Unbox` expression, whose sign is computed based on
* the sign of its operand and the source and destination types.
*/
abstract private class CastSignExpr extends FlowSignExpr {
SemUnaryExpr cast;
CastSignExpr() { cast = this and cast instanceof SemCastExpr }
override Sign getSignRestriction() { result = semExprSign(cast.getOperand()) }
}
/**
* A `Convert` expression.
*/
private class ConvertSignExpr extends CastSignExpr {
override SemConvertExpr cast;
}
/**
* A `Box` expression.
*/
private class BoxSignExpr extends CastSignExpr {
override SemBoxExpr cast;
}
/**
* An `Unbox` expression.
*/
private class UnboxSignExpr extends CastSignExpr {
override SemUnboxExpr cast;
UnboxSignExpr() {
exists(SemType fromType | fromType = getTrackedType(cast.getOperand()) |
// Only numeric source types are handled here.
fromType instanceof SemNumericType
)
}
}
private predicate unknownSign(SemExpr e) { e instanceof UnknownSignExpr }
/**
* Holds if `lowerbound` is a lower bound for `v` at `pos`. This is restricted
* to only include bounds for which we might determine a sign.
*/
private predicate lowerBound(
SemExpr lowerbound, SemSsaVariable v, SemSsaReadPosition pos, boolean isStrict
) {
exists(boolean testIsTrue, SemRelationalExpr comp |
pos.hasReadOfVar(v) and
semGuardControlsSsaRead(semGetComparisonGuard(comp), pos, testIsTrue) and
not unknownSign(lowerbound)
|
testIsTrue = true and
comp.getLesserOperand() = lowerbound and
comp.getGreaterOperand() = semSsaRead(v, 0) and
(if comp.isStrict() then isStrict = true else isStrict = false)
or
testIsTrue = false and
comp.getGreaterOperand() = lowerbound and
comp.getLesserOperand() = semSsaRead(v, 0) and
(if comp.isStrict() then isStrict = false else isStrict = true)
)
}
/**
* Holds if `upperbound` is an upper bound for `v` at `pos`. This is restricted
* to only include bounds for which we might determine a sign.
*/
private predicate upperBound(
SemExpr upperbound, SemSsaVariable v, SemSsaReadPosition pos, boolean isStrict
) {
exists(boolean testIsTrue, SemRelationalExpr comp |
pos.hasReadOfVar(v) and
semGuardControlsSsaRead(semGetComparisonGuard(comp), pos, testIsTrue) and
not unknownSign(upperbound)
|
testIsTrue = true and
comp.getGreaterOperand() = upperbound and
comp.getLesserOperand() = semSsaRead(v, 0) and
(if comp.isStrict() then isStrict = true else isStrict = false)
or
testIsTrue = false and
comp.getLesserOperand() = upperbound and
comp.getGreaterOperand() = semSsaRead(v, 0) and
(if comp.isStrict() then isStrict = false else isStrict = true)
)
}
/**
* Holds if `eqbound` is an equality/inequality for `v` at `pos`. This is
* restricted to only include bounds for which we might determine a sign. The
* boolean `isEq` gives the polarity:
* - `isEq = true` : `v = eqbound`
* - `isEq = false` : `v != eqbound`
*/
private predicate eqBound(SemExpr eqbound, SemSsaVariable v, SemSsaReadPosition pos, boolean isEq) {
exists(SemGuard guard, boolean testIsTrue, boolean polarity |
pos.hasReadOfVar(v) and
semGuardControlsSsaRead(guard, pos, testIsTrue) and
guard.isEquality(eqbound, semSsaRead(v, 0), polarity) and
isEq = polarity.booleanXor(testIsTrue).booleanNot() and
not unknownSign(eqbound)
)
}
/**
* Holds if `bound` is a bound for `v` at `pos` that needs to be positive in
* order for `v` to be positive.
*/
private predicate posBound(SemExpr bound, SemSsaVariable v, SemSsaReadPosition pos) {
upperBound(bound, v, pos, _) or
eqBound(bound, v, pos, true)
}
/**
* Holds if `bound` is a bound for `v` at `pos` that needs to be negative in
* order for `v` to be negative.
*/
private predicate negBound(SemExpr bound, SemSsaVariable v, SemSsaReadPosition pos) {
lowerBound(bound, v, pos, _) or
eqBound(bound, v, pos, true)
}
/**
* Holds if `bound` is a bound for `v` at `pos` that can restrict whether `v`
* can be zero.
*/
private predicate zeroBound(SemExpr bound, SemSsaVariable v, SemSsaReadPosition pos) {
lowerBound(bound, v, pos, _) or
upperBound(bound, v, pos, _) or
eqBound(bound, v, pos, _)
}
/** Holds if `bound` allows `v` to be positive at `pos`. */
private predicate posBoundOk(SemExpr bound, SemSsaVariable v, SemSsaReadPosition pos) {
posBound(bound, v, pos) and TPos() = semExprSign(bound)
}
/** Holds if `bound` allows `v` to be negative at `pos`. */
private predicate negBoundOk(SemExpr bound, SemSsaVariable v, SemSsaReadPosition pos) {
negBound(bound, v, pos) and TNeg() = semExprSign(bound)
}
/** Holds if `bound` allows `v` to be zero at `pos`. */
private predicate zeroBoundOk(SemExpr bound, SemSsaVariable v, SemSsaReadPosition pos) {
lowerBound(bound, v, pos, _) and TNeg() = semExprSign(bound)
or
lowerBound(bound, v, pos, false) and TZero() = semExprSign(bound)
or
upperBound(bound, v, pos, _) and TPos() = semExprSign(bound)
or
upperBound(bound, v, pos, false) and TZero() = semExprSign(bound)
or
eqBound(bound, v, pos, true) and TZero() = semExprSign(bound)
or
eqBound(bound, v, pos, false) and TZero() != semExprSign(bound)
}
/**
* Holds if there is a bound that might restrict whether `v` has the sign `s`
* at `pos`.
*/
private predicate hasGuard(SemSsaVariable v, SemSsaReadPosition pos, Sign s) {
s = TPos() and posBound(_, v, pos)
or
s = TNeg() and negBound(_, v, pos)
or
s = TZero() and zeroBound(_, v, pos)
}
/**
* Gets a possible sign of `v` at `pos` based on its definition, where the sign
* might be ruled out by a guard.
*/
pragma[noinline]
private Sign guardedSsaSign(SemSsaVariable v, SemSsaReadPosition pos) {
result = semSsaDefSign(v) and
pos.hasReadOfVar(v) and
hasGuard(v, pos, result)
}
/**
* Gets a possible sign of `v` at `pos` based on its definition, where no guard
* can rule it out.
*/
pragma[noinline]
private Sign unguardedSsaSign(SemSsaVariable v, SemSsaReadPosition pos) {
result = semSsaDefSign(v) and
pos.hasReadOfVar(v) and
not hasGuard(v, pos, result)
}
/**
* Gets a possible sign of `v` at read position `pos`, where a guard could have
* ruled out the sign but does not.
* This does not check that the definition of `v` also allows the sign.
*/
private Sign guardedSsaSignOk(SemSsaVariable v, SemSsaReadPosition pos) {
result = TPos() and
forex(SemExpr bound | posBound(bound, v, pos) | posBoundOk(bound, v, pos))
or
result = TNeg() and
forex(SemExpr bound | negBound(bound, v, pos) | negBoundOk(bound, v, pos))
or
result = TZero() and
forex(SemExpr bound | zeroBound(bound, v, pos) | zeroBoundOk(bound, v, pos))
}
/** Gets a possible sign for `v` at `pos`. */
private Sign semSsaSign(SemSsaVariable v, SemSsaReadPosition pos) {
result = unguardedSsaSign(v, pos)
or
result = guardedSsaSign(v, pos) and
result = guardedSsaSignOk(v, pos)
}
/** Gets a possible sign for `v`. */
pragma[nomagic]
Sign semSsaDefSign(SemSsaVariable v) { result = v.(SignDef).getSign() }
/** Gets a possible sign for `e`. */
cached
Sign semExprSign(SemExpr e) {
exists(Sign s | s = e.(SignExpr).getSign() |
if
getTrackedType(e) instanceof SemUnsignedIntegerType and
s = TNeg() and
not Specific::ignoreTypeRestrictions(e)
then result = TPos()
else result = s
)
}
/**
* Dummy predicate that holds for any sign. This is added to improve readability
* of cases where the sign is unrestricted.
*/
predicate semAnySign(Sign s) { any() }
/** Holds if `e` can be positive and cannot be negative. */
predicate semPositive(SemExpr e) {
semExprSign(e) = TPos() and
not semExprSign(e) = TNeg()
}
/** Holds if `e` can be negative and cannot be positive. */
predicate semNegative(SemExpr e) {
semExprSign(e) = TNeg() and
not semExprSign(e) = TPos()
}
/** Holds if `e` is strictly positive. */
predicate semStrictlyPositive(SemExpr e) {
semExprSign(e) = TPos() and
not semExprSign(e) = TNeg() and
not semExprSign(e) = TZero()
}
/** Holds if `e` is strictly negative. */
predicate semStrictlyNegative(SemExpr e) {
semExprSign(e) = TNeg() and
not semExprSign(e) = TPos() and
not semExprSign(e) = TZero()
}

View File

@@ -1,23 +0,0 @@
/**
* Provides C++-specific definitions for use in sign analysis.
*/
private import experimental.semmle.code.cpp.semantic.Semantic
/**
* Workaround to allow certain expressions to have a negative sign, even if the type of the
* expression is unsigned.
*/
predicate ignoreTypeRestrictions(SemExpr e) { none() }
/**
* Workaround to track the sign of certain expressions even if the type of the expression is not
* numeric.
*/
predicate trackUnknownNonNumericExpr(SemExpr e) { none() }
/**
* Workaround to ignore tracking of certain expressions even if the type of the expression is
* numeric.
*/
predicate ignoreExprSign(SemExpr e) { none() }

View File

@@ -1,27 +0,0 @@
/**
* @name Print AST
* @description Outputs a representation of a file's Abstract Syntax Tree. This
* query is used by the VS Code extension.
* @id cpp/print-ast
* @kind graph
* @tags ide-contextual-queries/print-ast
*/
import cpp
import semmle.code.cpp.PrintAST
import definitions
/**
* The source file to generate an AST from.
*/
external string selectedSourceFile();
class Cfg extends PrintAstConfiguration {
/**
* Holds if the AST for `func` should be printed.
* Print All functions from the selected file.
*/
override predicate shouldPrintFunction(Function func) {
func.getFile() = getFileBySourceArchiveName(selectedSourceFile())
}
}

View File

@@ -1,9 +1,7 @@
name: codeql/cpp-all
version: 0.4.3-dev
groups: cpp
version: 0.0.2
dbscheme: semmlecode.cpp.dbscheme
extractor: cpp
library: true
upgrades: upgrades
dependencies:
codeql/ssa: ${workspace}
codeql/cpp-upgrades: 0.0.2

View File

@@ -84,7 +84,6 @@ private int fileHeaderLimit(File f) {
fc = fileFirstComment(f) and
result =
min(int line |
// code ending the initial comments
exists(DeclarationEntry de, Location l |
l = de.getLocation() and
l.getFile() = f and
@@ -106,13 +105,7 @@ private int fileHeaderLimit(File f) {
line > fc
)
or
// end of the file
line = f.getMetrics().getNumberOfLines()
or
// rarely, we've seen extremely long sequences of initial comments
// (and/or limitations in the above constraints) cause an overflow of
// the maximum string length. So don't look past 1000 lines regardless.
line = 1000
)
)
}

View File

@@ -111,6 +111,24 @@ class Class extends UserType {
result = this.getCanonicalMember(index).(TemplateVariable).getAnInstantiation()
}
/**
* DEPRECATED: Use `getCanonicalMember(int)` or `getAMember(int)` instead.
* Gets the `index`th member of this class.
*/
deprecated Declaration getMember(int index) {
member(underlyingElement(this), index, unresolveElement(result))
}
/**
* DEPRECATED: As this includes a somewhat arbitrary number of
* template instantiations, it is unlikely to do what
* you need.
* Gets the number of members that this class has. This includes both
* templates that are in this class, and instantiations of those
* templates.
*/
deprecated int getNumMember() { result = count(this.getAMember()) }
/**
* Gets a private member declared in this class, struct or union.
* For template members, this may be either the template or an
@@ -188,7 +206,26 @@ class Class extends UserType {
* it is callable by a particular caller. For C++11, there's also a question
* of whether to include members that are defaulted or deleted.
*/
deprecated predicate hasCopyConstructor() { this.getAMemberFunction() instanceof CopyConstructor }
deprecated predicate hasCopyConstructor() {
exists(CopyConstructor cc | cc = this.getAMemberFunction())
}
/**
* Holds if this class has a copy assignment operator that is either
* explicitly declared (though possibly `= delete`) or is auto-generated,
* non-trivial and called from somewhere.
*
* DEPRECATED: There is more than one reasonable definition of what it means
* to have a copy assignment operator, and we do not want to promote one
* particular definition by naming it with this predicate. Having a copy
* assignment operator could mean that such a member is declared or defined
* in the source or that it is callable by a particular caller. For C++11,
* there's also a question of whether to include members that are defaulted
* or deleted.
*/
deprecated predicate hasCopyAssignmentOperator() {
exists(CopyAssignmentOperator coa | coa = this.getAMemberFunction())
}
/**
* Like accessOfBaseMember but returns multiple results if there are multiple
@@ -200,7 +237,7 @@ class Class extends UserType {
exists(ClassDerivation cd | cd.getBaseClass() = base |
result =
this.accessOfBaseMemberMulti(cd.getDerivedClass(),
fieldInBase.accessInDirectDerived(cd.getASpecifier()))
fieldInBase.accessInDirectDerived(cd.getASpecifier().(AccessSpecifier)))
)
}
@@ -224,7 +261,8 @@ class Class extends UserType {
* includes the case of `base` = `this`.
*/
AccessSpecifier accessOfBaseMember(Declaration member) {
result = this.accessOfBaseMember(member.getDeclaringType(), member.getASpecifier())
result =
this.accessOfBaseMember(member.getDeclaringType(), member.getASpecifier().(AccessSpecifier))
}
/**
@@ -251,16 +289,6 @@ class Class extends UserType {
not this.implicitCopyConstructorDeleted() and
forall(CopyConstructor cc | cc = this.getAMemberFunction() |
cc.isCompilerGenerated() and not cc.isDeleted()
) and
(
not this instanceof ClassTemplateInstantiation
or
this.(ClassTemplateInstantiation).getTemplate().hasImplicitCopyConstructor()
) and
(
not this instanceof PartialClassTemplateSpecialization
or
this.(PartialClassTemplateSpecialization).getPrimaryTemplate().hasImplicitCopyConstructor()
)
}
@@ -276,18 +304,6 @@ class Class extends UserType {
not this.implicitCopyAssignmentOperatorDeleted() and
forall(CopyAssignmentOperator ca | ca = this.getAMemberFunction() |
ca.isCompilerGenerated() and not ca.isDeleted()
) and
(
not this instanceof ClassTemplateInstantiation
or
this.(ClassTemplateInstantiation).getTemplate().hasImplicitCopyAssignmentOperator()
) and
(
not this instanceof PartialClassTemplateSpecialization
or
this.(PartialClassTemplateSpecialization)
.getPrimaryTemplate()
.hasImplicitCopyAssignmentOperator()
)
}
@@ -303,7 +319,7 @@ class Class extends UserType {
exists(Type t | t = this.getAFieldSubobjectType().getUnspecifiedType() |
// Note: Overload resolution is not implemented -- all copy
// constructors are considered equal.
this.cannotAccessCopyConstructorOnAny(t)
this.cannotAccessCopyConstructorOnAny(t.(Class))
)
or
// - T has direct or virtual base class that cannot be copied (has deleted,
@@ -376,7 +392,7 @@ class Class extends UserType {
exists(Type t | t = this.getAFieldSubobjectType().getUnspecifiedType() |
// Note: Overload resolution is not implemented -- all copy assignment
// operators are considered equal.
this.cannotAccessCopyAssignmentOperatorOnAny(t)
this.cannotAccessCopyAssignmentOperatorOnAny(t.(Class))
)
or
exists(Class c | c = this.getADirectOrVirtualBase() |
@@ -404,10 +420,7 @@ class Class extends UserType {
* compiled for. For this reason, the `is_pod_class` predicate is
* generated by the extractor.
*/
predicate isPod() { is_pod_class(underlyingElement(this)) }
/** DEPRECATED: Alias for isPod */
deprecated predicate isPOD() { this.isPod() }
predicate isPOD() { is_pod_class(underlyingElement(this)) }
/**
* Holds if this class, struct or union is a standard-layout class
@@ -875,7 +888,7 @@ class NestedClass extends Class {
* pure virtual function.
*/
class AbstractClass extends Class {
AbstractClass() { this.getAMemberFunction() instanceof PureVirtualFunction }
AbstractClass() { exists(PureVirtualFunction f | this.getAMemberFunction() = f) }
override string getAPrimaryQlClass() { result = "AbstractClass" }
}
@@ -1060,6 +1073,31 @@ class PartialClassTemplateSpecialization extends ClassTemplateSpecialization {
override string getAPrimaryQlClass() { result = "PartialClassTemplateSpecialization" }
}
/**
* An "interface" is a class that only contains pure virtual functions (and contains
* at least one such function). For example:
* ```
* class MyInterfaceClass {
* public:
* virtual void myMethod1() = 0;
* virtual void myMethod2() = 0;
* };
* ```
*
* DEPRECATED: This class is considered to be too specific for general usage.
*/
deprecated class Interface extends Class {
Interface() {
forex(Declaration m |
m.getDeclaringType() = this.getABaseClass*() and not compgenerated(unresolveElement(m))
|
m instanceof PureVirtualFunction
)
}
override string getAPrimaryQlClass() { result = "Interface" }
}
/**
* A class/struct derivation that is virtual. For example the derivation in
* the following code is a `VirtualClassDerivation`:

View File

@@ -490,7 +490,8 @@ class AccessHolder extends Declaration, TAccessHolder {
*/
pragma[inline]
predicate canAccessMember(Declaration member, Class derived) {
this.couldAccessMember(member.getDeclaringType(), member.getASpecifier(), derived)
this.couldAccessMember(member.getDeclaringType(), member.getASpecifier().(AccessSpecifier),
derived)
}
/**

View File

@@ -6,7 +6,6 @@
import semmle.code.cpp.Location
private import semmle.code.cpp.Enclosing
private import semmle.code.cpp.internal.ResolveClass
private import semmle.code.cpp.internal.ResolveGlobalVariable
/**
* Get the `Element` that represents this `@element`.
@@ -29,12 +28,9 @@ Element mkElement(@element e) { unresolveElement(result) = e }
pragma[inline]
@element unresolveElement(Element e) {
not result instanceof @usertype and
not result instanceof @variable and
result = e
or
e = resolveClass(result)
or
e = resolveGlobalVariable(result)
}
/**
@@ -59,6 +55,9 @@ class ElementBase extends @element {
cached
string toString() { none() }
/** DEPRECATED: use `getAPrimaryQlClass` instead. */
deprecated string getCanonicalQLClass() { result = this.getAPrimaryQlClass() }
/**
* Gets a comma-separated list of the names of the primary CodeQL classes to which this element belongs.
*/
@@ -92,6 +91,13 @@ class Element extends ElementBase {
*/
predicate fromSource() { this.getFile().fromSource() }
/**
* Holds if this element may be from a library.
*
* DEPRECATED: always true.
*/
deprecated predicate fromLibrary() { this.getFile().fromLibrary() }
/** Gets the primary location of this element. */
Location getLocation() { none() }
@@ -113,7 +119,10 @@ class Element extends ElementBase {
then
exists(MacroInvocation mi |
this = mi.getAGeneratedElement() and
not hasCloserMacroInvocation(this, mi) and
not exists(MacroInvocation closer |
this = closer.getAGeneratedElement() and
mi = closer.getParentInvocation+()
) and
result = mi.getMacro()
)
else result = this
@@ -237,14 +246,6 @@ class Element extends ElementBase {
}
}
pragma[noinline]
private predicate hasCloserMacroInvocation(Element elem, MacroInvocation mi) {
exists(MacroInvocation closer |
elem = closer.getAGeneratedElement() and
mi = closer.getParentInvocation()
)
}
private predicate isFromTemplateInstantiationRec(Element e, Element instantiation) {
instantiation.(Function).isConstructedFrom(_) and
e = instantiation

View File

@@ -4,6 +4,7 @@
import semmle.code.cpp.Variable
import semmle.code.cpp.Enum
import semmle.code.cpp.exprs.Access
/**
* A C structure member or C++ non-static member variable. For example the
@@ -31,7 +32,7 @@ class Field extends MemberVariable {
int getByteOffset() { fieldoffsets(underlyingElement(this), result, _) }
/**
* Gets the byte offset within `mostDerivedClass` of each occurrence of this
* Gets the byte offset within `mostDerivedClass` of each occurence of this
* field within `mostDerivedClass` itself or a base class subobject of
* `mostDerivedClass`.
* Note that for fields of virtual base classes, and non-virtual base classes

View File

@@ -196,11 +196,31 @@ class Folder extends Container, @folder {
*/
deprecated string getName() { folders(underlyingElement(this), result) }
/**
* DEPRECATED: use `getAbsolutePath` instead.
* Holds if this element is named `name`.
*/
deprecated predicate hasName(string name) { name = this.getName() }
/**
* DEPRECATED: use `getAbsolutePath` instead.
* Gets the full name of this folder.
*/
deprecated string getFullName() { result = this.getName() }
/**
* DEPRECATED: use `getBaseName` instead.
* Gets the last part of the folder name.
*/
deprecated string getShortName() { result = this.getBaseName() }
/**
* DEPRECATED: use `getParentContainer` instead.
* Gets the parent folder.
*/
deprecated Folder getParent() {
containerparent(unresolveElement(result), underlyingElement(this))
}
}
/**
@@ -218,6 +238,8 @@ class Folder extends Container, @folder {
class File extends Container, @file {
override string getAbsolutePath() { files(underlyingElement(this), result) }
override string toString() { result = Container.super.toString() }
override string getAPrimaryQlClass() { result = "File" }
override Location getLocation() {
@@ -286,6 +308,13 @@ class File extends Container, @file {
*/
override predicate fromSource() { numlines(underlyingElement(this), _, _, _) }
/**
* Holds if this file may be from a library.
*
* DEPRECATED: For historical reasons this is true for any file.
*/
deprecated override predicate fromLibrary() { any() }
/** Gets the metric file. */
MetricFile getMetrics() { result = this }
@@ -399,3 +428,25 @@ class CppFile extends File {
override string getAPrimaryQlClass() { result = "CppFile" }
}
/**
* DEPRECATED: Objective-C is no longer supported.
* An Objective C source file, as determined by file extension.
*
* For the related notion of whether a file is compiled as Objective C
* code, use `File.compiledAsObjC`.
*/
deprecated class ObjCFile extends File {
ObjCFile() { none() }
}
/**
* DEPRECATED: Objective-C is no longer supported.
* An Objective C++ source file, as determined by file extension.
*
* For the related notion of whether a file is compiled as Objective C++
* code, use `File.compiledAsObjCpp`.
*/
deprecated class ObjCppFile extends File {
ObjCppFile() { none() }
}

View File

@@ -38,8 +38,8 @@ class Function extends Declaration, ControlFlowNode, AccessHolder, @function {
* int z = min(5, 7);
* ```
* The full signature of the function called on the last line would be
* `min<int>(int, int) -> int`, and the full signature of the uninstantiated
* template on the first line would be `min<T>(T, T) -> T`.
* "min<int>(int, int) -> int", and the full signature of the uninstantiated
* template on the first line would be "min<T>(T, T) -> T".
*/
string getFullSignature() {
exists(string name, string templateArgs, string args |

Some files were not shown because too many files have changed in this diff Show More