Group of Software Security In Progress

GoSSIP @ LoCCS.Shanghai Jiao Tong University

Do Not Trust Me Using Malicious IdPs for Analyzing and Attacking Single Sign-On

论文下载

Background

之后会用到的各种概念

  • Code Fragment(CF):用来检测的对象,可以是一个文件,一个函数,甚至一个代码块。
  • Code Clone: 有相似性函数f, 如果f(CF1) == f(CF2)则判定两个CF相同。
  • Clone Type:
    • Type 1: 只有空格,布局,注释不同
    • Type 2: identifiers(变量名、结构体名称、函数名),literals(字面值),变量类型以及Type1中提到的内容有所不同
    • Type 3: 还有一些语句的增删的情况的出现
    • Type 4: 两个CF实现同一功能,但是使用不同syntactic variants(语法)实现

Clone Detection Process

本节总结了通常情况下进行Code Clone检测的步骤,所有步骤不一定是必须的:

  • Preprocessing 预处理:
    • 删除无关内容:
      • 注释
      • Java中嵌入的SQL语句,C中嵌入的汇编。(如果工具是针对某一特定语言的)
      • 类似YACC生成的代码
    • 用断开的代码片段获得完整的单元(函数,类,语句块)
    • 提取用于比较的代码单元:
      • 根据检测算法的不同,可能需要提取line, token;
      • 一个if 语句也可能需要切分成:条件、then 语句块、else 语句块
  • Transformation
    • Extraction: 如果检测方法不是纯文本textual的,通常需要将代码转换为中间表达
      • Tokenization: token-based的方法会将代码中的token提取,生成token序列,然后比较token序列的相似程度
      • Parsing: 通过将代码转换成抽象语法树AST,再寻找相似子树,来寻找code clone。一些Metrics-Based的方法也需要这一步骤
      • Control & Data Flow Analysis: 寻找同构,用于生成Metric
    • Normalization: 删除空格、注释,Normalize标识符,对代码进行小幅修改(比如删除static 关键字)
  • Match Detection:
  • Formatting: 返回原始的相似CF对
  • Post-processing / Filtering:相似的CF可能有很多
    • 人工筛选:需要系统提供一个易读的结果,(HTML报告)来协助手工过滤
    • 根据CF的出现频率,长度,等等做启发式的分级或者过滤
  • Aggregation:将clone区分成不同的clone class(Type 1 ~ 4)

Overview of Clone Detection Techniques and Tools

  • Textual approaches:
    1. Johnson: window, hash lines
    2. Manber: 每行第一个关键字的序列
    3. Ducasse: 点图,如果CF1的x行和CF2的y行相同 ,就在图中绘制点(x, y),然后在图中寻找斜率为1的线段
    4. Wettel & Marinescu, SDD: 基于Ducasse,只相同的行附近寻找
    5. NICAD: 没说细节
    6. Marcus and Maletic: 用机器学习处理自然语言的方式,处理注释和identifiers(latent semantic indexing)
  • Lexical approaches:
    1. Dup: 提取出token, 将identifier和字面值都用它是本行第几个token代替,然后将整个token序列构造出后缀树,如果两个后缀有相同的前缀,那么久表示前缀出现了多次。可以检查出Type 1 和Type 2,和部分Type 3的情况(不超过阈值的话)
    2. CCFinder: 额外的normaliztion, if (a) b; 转化为 if (a) {b;},然后使用Dup的方法
    3. Gemini, RTF: 附加功能(散点图绘制,用户定制tokenization的方式),效率上的提升(后缀数组)
    4. CP-Miner: subsequence
  • Syntactic approaches:
    • Tree Matching
      • CloneDr: 编译器生成AST, 子树首先被分类,每个子类中的子树使用tree match比对
      • Wahler: AST to XML, and data mining.
      • Evans: Structural abstraction,把AST再抽象到高层,没提细节
      • Koschke, Phoenix: 获得AST 的前缀表达式,再用Lexical的方法快速寻找clone
      • Deckard:构建tree的特征向量,用LSH分类,然后再进一步寻找clone
    • Metrics-Based:
      • Mayrand: AST, CFG,用name, layout, expression, control flow的一些Metric
      • Kontogiannis: 5个Metric & diff距离
      • Balazinska:类似,用Metric 和 dynamic matching
      • Davey: 代码块的布局特征(缩进长度,),和关键字的数量 共300维的特征向量,然后用人工神经网络
  • Semantic approaches:
    • 获得PDG, 然后寻找同构或者相似子图

Comparison of Tools

罗列了各个工具的特点,包括:

  • 可用性(平台,外部依赖,使用协议)
  • 交互(是否有交互式界面,输出形式,IDE support)
  • 语言(何种(函数式、面向对象、过程),具体什么语言)
  • Clone 信息:(粒度(函数,基本快,代码,类,可变的)、类型(Type 1~4)、)
  • Technical Aspect Facets(比较方式,比较粒度(图,token),计算复杂度)
  • Adjustment(preprocess&post-process)
  • 预处理(方式,代码中间表达的形式)
  • 实验(有无完整的实验,结果,实验对象)

Scenario-Based Evaluation of the Techniques and Tools

实验结果是作者根据以往的文献总结,或者根据技术特征进行估计的

  • 对应四个Type,分别有四个Scenario, 然后每个Scenario 有几个不同的情况

Fig