const __m256i ShuffleRev = _mm256_set_epi8( 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15, // first 128-bit lane 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15// second 128-bit lane ); // Load 32 elements at once into one 32-byte register __m256i x = _mm256_loadu_si256( reinterpret_cast<__m256i*>(&Array8[i]) ); // Reverse each the bytes in each 128-bit lane x = _mm256_shuffle_epi8(x,ShuffleRev);
简而言之,分析器是一个源码的模拟器,追踪其可能的执行路径。程序状态(变量和表达式的值)被封装为 ProgramState 。程序中的位置被叫做 ProgramPoint 。state 和 program point 的组合是 ExplodedGraph 中的节点。术语“exploded”来自控制流图(control-flow graph,CFG)中爆炸式增长的控制流连边。
概念上讲,分析器会沿着 ExplodedGraph 执行可达性分析(reachability analysis)。从具有 entry program point 和 initial state 的根节点开始,分析模拟每个单独表达式的转移。表达式分析会产生状态改变,使用更新后的 program point 和 state 创建新节点。当满足某些 bug 条件时(违反检测不变量,checking invariant),就认为发现了 bug 。
分析器通过推理分支(branches)追踪多条路径(paths),分叉状态:在 true 分支上认为分支条件为 true,在 false 分支上认为分支条件为 false 。这种“假设”创建了程序中的值的约束(constraints),这些约束被记录在 ProgramState 对象(通过 ConstraintManager 修改)。如果假设分支条件会导致不能满足约束,这条分支就被认为不可行,路径也不会被选取。这就是我们实现路径敏感(path-sensitivity)的方式。我们降低了缓存节点的指数爆炸。如果和已存在节点含相同 state 和 program point 的新节点将被生成,路径会“出缓存”(caches out),我们只简单重用已有节点。因此 ExplodedGraph 不是有向无环图(DAG),它可以包含圈(cycles),当路径相互循环,以及出缓存。
let ParentPackage = Core in { // ... def MyChecker : Checker<"MyChecker">, HelpText<"Check for zero malloc">, Documentation<HasDocumentation>; // ... } // end "core"
voidPointerSubChecker::checkPreStmt(const BinaryOperator *B, CheckerContext &C)const{ // When doing pointer subtraction, if the two pointers do not point to the // same memory chunk, emit a warning. if (B->getOpcode() != BO_Sub) return;
// Allow arithmetic on different symbolic regions. if (isa<SymbolicRegion>(BaseLR) || isa<SymbolicRegion>(BaseRR)) return;
if (ExplodedNode *N = C.generateNonFatalErrorNode()) { if (!BT) BT.reset( newBuiltinBug(this, "Pointer subtraction", "Subtraction of two pointers that do not point to " "the same memory chunk may cause incorrect result.")); auto R = std::make_unique<PathSensitiveBugReport>(*BT, BT->getDescription(), N); R->addRange(B->getSourceRange()); C.emitReport(std::move(R)); } }
The “Building a Checker in 24 hours” presentation given at the November 2012 LLVM Developer’s meeting. Describes the construction of SimpleStreamChecker
intboolAND() { int val = boolexp(); while (token == AND) { match(AND); if (val == 0) return0; // short cut val = val & boolexp(); if (val == 0) return0; } return val; }
intboolOR() { int val = boolAND(); while (token == OR) { match(OR); if (val == 1) return1; // short cut val = val | boolAND(); } return val; }