sea dsa下载 - sea dsa源代码下载

sea dsa

其他类别

1.0.0

下载

SEADSA：用于验证低级C/C ++的点对点分析

SeaDsa是一个受DSA启发的LLVM比特码的上下文，字段和数组敏感的点对点分析。 SeaDsa是比Dsa更可扩展和精确的数量级，并且由于上下文灵敏度的处理，添加了部分流动敏感性和类型意识，因此SeaDsa的先前实现。

尽管SeaDsa可以分析任意LLVM比特码，但已针对C/C ++程序的程序验证进行了定制。它可以用作独立工具，也可以与海角验证框架及其分析一起使用。

该分支支持LLVM 14。

要求

SeaDsa用C ++编写，并使用Boost库。主要要求是：

C ++支持C ++ 14
Boost> = 1.65
LLVM 14

要运行测试，请安装以下软件包：

sudo pip install lit OutputCheck
sudo easy_install networkx
sudo apt-get install libgraphviz-dev
sudo easy_install pygraphviz

项目结构

主点对图数据结构， Graph ， Cell和Node在include/Graph.hh和src/Graph.cc中定义。
本地分析include/Local.hh和src/DsaLocal.cc 。
自下而上的分析include/BottomUp.hh和src/DsaBottomUp.cc 。
自上而下的分析在include/TopDown.hh和src/DsaTopDown.cc中。
概要室节点克隆器中include/Cloner.hh和src/Clonner.cc 。
类型处理代码在include/FieldType.hh中， include/TypeUtils.hh src/FieldType.cc src/TypeUtils.cc 。
分配器函数发现在include/AllocWrapInfo.hh和src/AllocWrapInfo.cc中。

汇编和用法

程序验证基准

可以在TEA-DSA-EXTRAS中找到有关运行程序验证基准的说明，以及用于构建现实世界项目的食谱以及我们的结果。

集成在其他C ++项目中（用于用户）

SeaDsa包含两个目录： include和src 。由于SeaDsa分析了LLVM比特码，因此使用SeaDsa构建时必须访问LLVM标头文件和库。

如果您的项目使用cmake ，则只需要添加项目的CMakeLists.txt ：

 include_directories(seadsa/include)
 add_subdirectory(seadsa)

独立（用于开发人员）

如果您已经在计算机上安装了llvm-14 ：

 mkdir build && cd build
cmake -DCMAKE_INSTALL_PREFIX=run -DLLVM_DIR=__here_llvm-14__/share/llvm/cmake  ..
cmake --build . --target install

否则：

 mkdir build && cd build
cmake -DCMAKE_INSTALL_PREFIX=run ..
cmake --build . --target install

进行测试：

 cmake --build . --target test-sea-dsa

可视化存储器图和完整的呼叫图

考虑一个称为tests/c/simple.c的C程序：

 #include <stdlib.h>

typedef struct S {
  int * * x ;
  int * * y ;  
} S ;

int g ;

int main ( int argc , char * * argv ){

  S s1 , s2 ;

  int * p1 = ( int * ) malloc ( sizeof ( int ));
  int * q1 = ( int * ) malloc ( sizeof ( int ));  
  s1 . x = & p1 ;
  s1 . y = & q1 ;    
  * ( s1 . x ) = & g ;
  
  return 0 ;
}

生成比特代码：

 clang -O0 -c -emit-llvm -S tests/c/simple.c -o simple.ll

选项-O0用于禁用clang优化。通常，启用clang优化是一个好主意。但是，对于诸如simple.c之类的琐碎示例，Clang简化了太多，因此不会观察到任何有用的东西。选项-c -emit-llvm -S以人类可读格式生成比特码。

在比特码上运行sea-dsa并打印内存图到点格式：

 seadsa -sea-dsa=butd-cs -sea-dsa-type-aware -sea-dsa-dot  simple.ll

选项-sea-dsa=butd-cs -sea-dsa-type-aware可以在我们的FMCAD'19论文中实施的分析（请参阅参考文献）。此命令将在BitCode程序中为每个函数FUN生成一个FUN.mem.dot文件。在我们的情况下，唯一的函数是main ，因此，有一个名为main.mem.dot的文件。该文件是在当前目录中生成的。如果要将.dot文件存储在其他目录DIR中，请添加选项-sea-dsa-dot-outdir=DIR

通过将其转换为pdf文件，可视化main.mem.dot ：

 dot -Tpdf main.mem.dot -o main.mem.pdf
 open main.mem.pdf  // replace with you favorite pdf viewer

记忆图的示例

在我们的内存模型中，指针值由一个单元格表示，该单元格是一对内存对象和偏移。内存对象在内存图中表示为节点。边缘在细胞之间。

每个节点字段代表一个单元格（即节点中的偏移）。例如，节点字段<0,i32**>和<8,i32**>分别由%6和%15指向，是来自同一内存对象的两个不同的单元格。字段<8,i32**>表示相应内存对象中偏移8的单元格，其类型为i32** 。黑色边缘代表细胞之间的点对点关系。它们标记为代表目标节点中偏移的数字。蓝色边缘将功能的形式参数与单元格连接。紫色边缘将LLVM指针变量与单元格连接。节点可以具有诸如S （堆栈分配的内存）， H （堆分配内存）， M （修改后的内存）， R （读取存储器）， E （外部分配的内存）等等标记。标签{void}用于表示该节点已分配，但该程序尚未使用该节点。

sea-dsa还可以解决间接电话。间接呼叫是一个呼叫，其中callee在静态上不知道。 sea-dsa识别间接呼叫的所有可能级别，并生成LLVM呼叫图作为输出。

在tests/c/complete_callgraph_5.c中考虑此示例：

 struct class_t ;
typedef int ( * FN_PTR )( struct class_t * , int );
typedef struct class_t {
  FN_PTR m_foo ;
  FN_PTR m_bar ;
} class_t ;

int foo ( class_t * self , int x )
{
  if ( x > 10 ) {
    return self -> m_bar ( self , x + 1 );
  } else
    return x ;
}

int bar ( class_t * self , int y ) {
  if ( y < 100 ) {
    return y + self -> m_foo ( self , 10 );
  } else
    return y - 5 ;
}

int main ( void ) {
  class_t obj ;
  obj . m_foo = & foo ;
  obj . m_bar = & bar ;
  int res ;
  res = obj . m_foo ( & obj , 42 );
  return 0 ;
}

输入命令：

 clang -c -emit-llvm -S tests/c/complete_callgraph_5.c  -o ex.ll
sea-dsa --sea-dsa-callgraph-dot ex.ll

它在当前目录中生成一个名为callgraph.dot的.dot文件。同样， .dot文件可以转换为.pdf文件并使用命令打开：

 dot -Tpdf callgraph.dot -o callgraph.pdf
open callgraph.pdf

呼叫图的示例

sea-dsa还可以打印一些有关呼叫图分辨率过程的统计信息（请注意，您需要用-g调用clang以打印文件，行和列信息）：

 sea-dsa --sea-dsa-callgraph-stats ex.ll


=== Sea-Dsa CallGraph Statistics === 
** Total number of indirect calls 0
** Total number of resolved indirect calls 3

%16 = call i32 %12(%struct.class_t* %13, i32 %15) at tests/c/complete_callgraph_5.c:14:12
RESOLVED
Callees:
  i32 bar(%struct.class_t*,i32)
  
%15 = call i32 %13(%struct.class_t* %14, i32 10) at tests/c/complete_callgraph_5.c:23:16
RESOLVED
Callees:
  i32 foo(%struct.class_t*,i32)
  
%11 = call i32 %10(%struct.class_t* %2, i32 42) at tests/c/complete_callgraph_5.c:36:9
RESOLVED
Callees:
  i32 foo(%struct.class_t*,i32)

处理C/C ++库和外部呼叫

可以通过编写呼叫包装器来定义外部呼叫的指针语义，该包装器调用seadsa/seadsa.h中定义的任何功能中的任何一个。

extern void seadsa_alias(const void *p, ...);
extern void seadsa_collapse(const void *p);
extern void seadsa_mk_seq(const void *p, unsigned sz);

seadsa_alias统一了所有参数的细胞， seadsa_collapse告诉sea-dsa崩溃（即，野外敏感性丧失） p指向P指向的细胞， seadsa_mk_seq告诉sea-dsa将其标记为序列为序列，该节点由p size sz pose o。

例如，考虑一个外部呼叫foo定义如下：

 extern void* foo(const void*p1, void *p2, void *p3);

假设返回的指针应统一为p2 ，而不是p1 。另外，我们希望折叠与p3相对应的细胞。然后，我们可以用以下定义替换上述foo的原型：

 #include "seadsa/seadsa.h"
void* foo(const void*p1, void *p2, void*p3) {
	void* r = seadsa_new();
	seadsa_alias(r,p2);
	seadsa_collapse(p3);
	return r;
}