背景

• 为了去抓取应用端发来的负载信息，比如sql,timestamp,sql中的para,和select语句的result集合，通过分析这些负载，来模拟负载，主要用于抓取应用端的负载，相当于数据挖掘中获取数据的来源把~~

• 这篇主要是总结我在适配skywalking获取mysql应用端的负载遇到的问题和感受。

先行

• 利用skywalking在以mysql为数据库的应用程序中抓取负载，在实验中，以oltpbench为应用端。大致的配置是，在https://github.com/apache/skywalking拉去skywalking源代码，利用说明文档进行编译

  1 2 3 4 5

  git clone https://github.com/apache/skywalking.git cd skywalking/ git submodule init git submodule update ./mvnw clean package -DskipTests

• 编译好的在dist目录下，如果没有别的需求，可直接在启动应用端的脚本或命令行中加入-javaagent /skywalking/agent/skywalking-agent.jar。

• 由于项目中需要按照一定的形式将抓取到的日志输入固定的文件中，因此主要对skywalking的三个包进行修改，分别是mysql-common,mysql-5.x,jdbc-commons，这三个都在./apm-sniffer/apm-sdk-plugins中。

操作

mysql-commons

• 里面都是一些截流器，有针对预编译sql的PreparadStatementExeucute，还有PreparadStatementBatchExeucute，和普通的StateExecute。这些截流器都被注册了，与mysql-5.x中的注册器对应，注册器指明mysql中哪里函数利用那些截流器去捕获。如”add batch”函数就利用PreparadStatementBatchExeucute去抓取。”executeUpdate”利用PreparadStatementExeucute和StateExecute去抓取（根据不同的sql类型）

mysql-5.x

• 一些注册器，与拦截器对应即可

jdbc-commons

• 主要是加了connId，还有与commit,rollback有关的拦截器，在这个包中，也进行了修改。

问题

mysql 的 jdbc重复调用问题

• 查看Mysql的jdbc的包（可利用反编译软件进行查看），发现add batch又调用了executeUpdate函数，导致skywalking抓包的时候重复捕获一条语句，导致重复。此外，还有executeUpdate自调用三次，导致一条日志被打印出三次。这类问题的处理方式，利用查看调用栈，分析它的调用过程，来忽略一些日志的输出。

• 1 2 3 4 5 6 7 8 9

  Exception ex = new Exception(); StackTraceElement[] ste = ex.getStackTrace(); boolean fromExecuteBatch = false; for (int i = 0; i < ste.length; ++i) { if(ste[i].getMethodName().contains("executeBatch")||ste[i].getMethodName().contains("executeUpdate$Original")){ fromExecuteBatch = true; break; } }

mysql中以一个host为一个connId

• 由于项目的需要，我们需要得到connId，在jdbc-commons的相应位置加上与connId相关的代码。
• 但是发现createstatement有个问题，就是无论多少个线程，以及无论多少个连接，但输出总是一个相同的。但从mysql端捕获到的connectionInfo都是不同的，后来发现是skywalking中是根据host和Port来存储connectionInfo的，若从相同的host和port发送数据库请求，那skywalking（mysql部分，oracle应该不是这样的)就认为是用一条connectionInfo信息，导致出错。
• 这个问题的解决方法：就不用host和port进行存储..换了另一种方式。

总结

• skywalking适配mysql耗时达1周左右，发现自己还是畏惧源码的阅读，无论是skywalking还是mysql-jdbc还是不能有效的进行阅读，希望下次能改进。
• 自己对于问题的解决不能深入，抱着懒散的心态~，要加油呀！

Motivation

• 数据库即服务（DBaaS)目前很流行，云计算的出现，让很多开发人员都直接使用云上数据库而不用自己去搭建一个数据库，这扩展了数据库的使用，但很多开发人员没有数据库相关知识，可能写出来的sql语句存在APs（Anti-Patterns)，而APs会影响访问数据库时的性能，进而对应用产生影响。因此，这篇文章站在这个角度，去检测sql语句是否存在APs，并且将sql中存在的APs进行排序（这里主要是为了修复主要影响性能的APs，因为修复APs可能修改数据库schema等等，会对其他的sql产生一定影响），最后对主要的APs进行自动修复（实质上这篇文章是按照现有的规则进行修复）。

Challenge

• AP可能违反基本数据库设计原则（如，参照一致性等等）

Contribution

• 讲述了如今其他识别APs的工具的局限性

• 注意：detection是有按照一定的rule进行匹配来将AP侦测出来

• Detection：将query和data分析相结合进行AP侦测。

• Rank：针对APs上的性能数据进行建模，获取rank model。

• Fix：基于规则query重构技术提出fix APs的建议。

Background

Classification of Anti-Patterns

Impact of Anti-Patterns

• Performance：性能，如吞吐和延迟
• Maintainability:当业务发生了改变，应用设计和组件被修改的容易程度（这里指sql和schema）
• Accuracy:存进去的数据和读出来的时候是否还是一致的（如，浮点数的精度是否丢失了，考虑数据库schema的column类型定义的如何）

System Overview

• ap-detect:静态分析queries，分析数据库中的数据和元数据
• ap-rank：根据detect出来的AP对各类评价指标的影响排序（文中设置user-study,由于可以根据自己的应用需求调整不同评价指标的权重，如读事务多的应用场景对读性能更为看重）
• ap-fix：根据定义好的rule来对AP进行fix（也就是说rule是有限的，无法cover到全部，这里detect从后面的实验来看也应该是有限的AP，就是定义的AP越多识别出来的也越多…）

Finding Anti-Patterns

• Query-Analyser：获取query的column name、table names、predicates、constraints和indexes等等（就是一些logical feature)
• Data-Analyser：获取数据库中表的每个Column的数据分布和format（类型？）等
• Query-Rules：根据建立好的rules识别APs判别query是否存在APs
• Data-Rules：根据建立好的rules识别APs判别data是否存在APs

Query Analysis

• intra-query detection：从单条sql获取context，使用预定好的rule（rule里由一系列函数组成）去detect，使用no-validating parsing logic来支持不同数据库的查询，返回annotating the parse tree(ap-detect和ap-fix使用这个去找到APS)
• inter-query detection：从sql和sql之间获取context，利用整个应用的context，不一定是相邻的,在 Intra-query上多包涵了两个组件：schama和与应用相关的queries

Data Analysis

• 首先scan数据库收集【收集代价大，定期执行】：
  • tables的schemata
  • 数据在相关column上的分布（e.g., unique values,mean, median等等）
• 还是根据相应的规则去check构建好的context中是否存在APs

Ranking Anti-Patterns

Metrics for Ranking Anti-Patterns

• Read and Write Performance (RP, WP)：读写性能。通过如果修复好这个AP能获取多少倍的加速。这个指标作为rank依据。
• Maintainability (M)：可维护性 是根据支持新的task时，数据库 在存在这个AP和不存在这个AP需要重构时改变的Number的差异,当number高度依赖于应用中的queries数时，这个AP优先级就会很高。
• Data Amplification (DA)：冗余的列，如age和出生年月；各种冗余不必要的信息。
• Data Integrity (DI): 更新是否保证数据库中保存的是想要的数据
• Accuracy (A): 如是否满足参照一致性

Model for Ranking Anti-Patterns

• 运用开发人员根据自己的开发需求去设置上方metrics的权重。（实际上开发人员也很难去做到这个，这里可以做一个权重自动化设置工具）
• 当APs之间发生冲突时，即修复一个AP会影响恶化另外一个AP，那就选择优先级高的AP进行修复

Fixing Anti-Patterns

• 自动推荐合适应用场景的数据库设计和queries。

• 两部分的query需要transform: 1. 具有APs的部分 2. 修改APsquery会影响的部分query
• 如果产生模糊的转换，那就返回一个textual fix，就是说这个工具不足够帮你fix…那它告诉你啥textual fix呢，让开发人员自己看着做
• 绿色部分解析： 如果query transformation清晰，那就把它解析成语法树，之后转换成sql语句。（数据库的语法树解析感觉有时间可以看看）

Query Repair Engine

• rule system是可扩展的，开发人员可以自己把rule按照一定的要求加进去。
• 首先，规则系统范式使得ap-fix很容易利用修复规则之间复杂的触发交互，从而避免了显式布局流的需要 规则之间的控制（这里没看懂，就直接有道翻译了一下）

Rule Representation:

• 每条规则都包含一个detection function和一个action function

Implementation

• 提供了三个接口：

  • Interactive Shell:

    1 2 3 4

    # Import the anti-pattern finder method from sqlcheck.finder import find_anti_patterns query = `INSERT INTO Users VALUES (1, 'foo')` results = find_anti_patterns(query)

• REST Interface

  1 2	HTTP POST /api/check Body: {"query":"INSERT INTO Users VALUES (1,'foo')"}

• GUI Interface

• 扩展性

  • 通用的规则接口（name, type, detection rule, ranking metrics, and repair rule）
  • context builder：增加应用的context来支持复杂rules
  • 用DBMS-specific解析器代替no-validating解析器

Evaluation

• 与DBDEO进行比较（Digital Equipment Corporation. 1992. SQL-92 Standard.

  https://www.contrib.andrew.cmu.edu/~shadow/sql/sql1992.txt.）

Detection of Anti-Patterns

• AP-coverage
• accuary
• Dialect-Coverage：可以适用哪些DBMS

Ranking and Repair of Antipatterns

• 针对几个类型的AP进行讨论
  • 索引过度使用
  • 索引使用不足
  • 不存在外键
  • 枚举类型（只有那几个数值）

User Study

• 招募23个学生去
  • construst SQL queries
• 使用GUI 界面追踪这些信息：
  • the original SQL queries
  • the fixes suggested by sqlcheck for the APs detected in the original queries
  • the re-formulated SQL queries developed by the user that incorporate these fixes.
• Web Applications & Databases
  • 收集github上的sql query，检测人家的应用的query是否存在APs，若存在就在别人的issues中提建议或是给别人发邮件，看看 别人的回馈意见。
• Limitations And Future Work
  • 都是根据定好的rules来发现APs的，对于新的不在规则中的APs不能后发现

TOREAD

• Tushar Sharma, Marios Fragkoulis, Stamatia Rizou, Magiel Bruntink,and Diomidis Spinellis. 2018. Smelly relations: measuring and understanding database schema quality. In Proc. of ICSE. ACM, 55–64.
• [21] Cunningham & Cunningham Inc. 2014. C2 Wiki. http://wiki.c2.com/?AntiPatternsCatalog

对负载生成的启发点

• 分析数据特征的时候，获取data在相关列上的分布情况，如Unique values,mean,median等（这里lauca貌似没有使用这些特征）

研究的主要方向

• 与SQL Anti-pattern有关，找到、排序（该APs对性能产生影响的大小）、修复APs

各项性能指标

• Read and Write Performance (RP, WP)
• Maintainability (M)
• Data Amplification (DA)
• Data Integrity (DI)
• Accuracy (A)

基本知识

数据库即服务

• DBaaS是一种云计算服务模型，用户只需要访问数据库即可，无需设置物理硬件，安装软件或配置性能。
• Schemate即schema的复数形式，包括table、column、data type、view、stored procedures、relationships、primary key、foreign key等

Adjacency List

• 具有层次结构的数据

• 解决方法：邻接表、路径枚举(Path Enumeration)、嵌套集(Nested Sets)、闭包表(Closure Table)

  • 邻接表：在树中检索指定节点的祖先节点是很昂贵的
  • 路径枚举：将祖先存储成字符串(以路径的形式)，缺点：数据库不能强制规定路径是正确形成的，或者路径中的值对应于存在的节点。维护路径字符串取决于应用程序代码，并验证它的开销是非常昂贵的。

  

  • 嵌套集：根据深度优先额外维护nsleft和nsright，便于寻找节点的所有祖先节点和所有的孩子结点，但插入和移动节点很复杂，需要重复编号nsleft和nsright，当树的使用设计频繁的插入，嵌套集不是最佳选择。

    

  

  • 闭包表：多增加一个表结构，专门用来存所有的祖孙信息，不只是父子信息，更便于查询。

  

基础知识

使用MySQL基本指令

• use database1; 切换数据库
• SHOW DATABASES; 显示所有数据库
• SHOW TABLES;
• SHOW COLUMNS FROM customers ; === DESCRIBE CUSTOMERS;

limit关键字：

• Limit 3,4 ==LIMIT 4 OFFSET 3; 从行3开始，返回4行；检索出来的第一行是行0

ORDER BY

• 通常ORDER BY子句中使用的列将是为显示所选择的列。但是，实际上并不一定，用非检索的列排序数据是完全合法的。
• 默认是升序
• 对于文本性的数据进行排序时，A被视为与a相同，这是MySQL（和大多数数据库管理系统）的默认行为。但是，许多数据库管理员能够在需要时改变这种行为。

使用IN操作的优点

• 语法更清楚且直观
• 一般比OR操作符清单执行更快
• 最大优点是可以包含其他SELECT语句，使得能够更动态地建立WHERE子句。

MySQL中NOT

• 支持对IN、BETWEEN和EXISTS子句取反，这与多数其他DBMS允许使用NOT对各种条件取反有很大的差别。

SQL中的谓词

• 谓词与函数的区别：对于通常的函数来说，返回值有可能是数字、字符串或者日期等，但是谓词的返回值都是真值（true/false/unknown）。

• LIKE、BETWEEN、IS NULL、IS NOT NULL、IN、EXISTS

  • LIKE——字符串的部分一致查询（模糊查询）

    1 2 3 4 5 6 7

    ①前方一致select * from user where username like 'aaa%'; ②中间一致select * from user where username like '%aaa%'; ③后方一致select * from user where username like '%aaa'; %可以匹配0个字符。

  • BETWEEN（and）——范围查询

用通配符的技巧

• 不要过度使用通配符，注意通配符的位置。

MySQL的正则表达式

• REGEXP和LIKE的区别：LIKE匹配整个串而REGEXP匹配子串

• 不区分大小写，为区分大小写，可使用BINARY关键字

  1	WHERE prod_name REGEXP BINARY 'JetPack .000'

• 进行OR匹配 ‘|’

• 匹配几个字符之一 [123] 表示匹配1或2或3，与1|2|3不同，前者是[1|2|3]的缩写

  1 2 3 4

  SELECT prod_name From products WHERE prod_name REGEXP '[123] Ton' ORDER BY prod_name;

• 匹配范围 [1-3]

  1 2 3 4

  SELECT prod_name From products WHERE prod_name REGEXP '[1-3] Ton' ORDER BY prod_name;

• 匹配特殊字符，如 . [] | () ，用\\为前导，如\\.表示查找. \\也用来引用元字符

• 匹配字符类

  

匹配多个实例

• 对匹配的数目进行更强的控制

  

  匹配定位符

• 为了匹配特定位置的文本

  

  • ^的双重用途：

    • 在集合中[]，用它来否限定该集合

    • 用来指串的开始处

创建计算字段

拼接：

• 多数DBMS使用+或者||来实现拼接，MySQL则使用Concat()函数来实现。

  1 2 3 4 5

  Select Concat(vend_name,'(',vend_country,')') From vendors ORDER BY vend_name; Return: ACME(USA)

• RTrim()函数： 删除数据右侧多余的空格。如RTrim(vend_name)

• LTrim()函数：去掉串左边的空格

• Trim()函数：去掉串左右两边的空格

• 取列的别名

使用数据处理函数

• 以下的函数都是大多数SQL实现支持的。

文本处理函数：

• 其中SOUNDEX()考虑了类似的发音字符和音节，使得能对串进行发音比较而不是字母比较。

日期和时间处理函数

• MySQL使用的日期格式，不管是插入或更新表值还是用WHERE子句进行过滤，日期必须为格式yyyy-mm-dd。

数值处理函数

• 在主要DBMS的函数中，数值函数是最一致最统一的函数

  

汇总数据

聚集函数

• Distinct关键字：后面必须使用列名。

分组数据

• 使用WITH ROLLUP关键字，可以得到每个分组以及每个分组汇总级别（针对每个分组）的值

  1 2 3

  SELECT vend_id,COUNT(*) AS num_prods FROM products GROUP BY vend_id WITH ROLLUP;

• WHERE过滤行，HAVING过滤分组

联结表

• 笛卡尔积：由没有联结条件的表关系返回的结果

• 内部联结，也称为等值联结

  • ANSI SQL规范首选INNER JOIN语法，而不是=

    1 2 3

    SELECT vend_name,prod_name,prod_price FROM vendors INNER JOIN products ON vendors.vend_id = products.vend_id;

乱七八糟

• 没有主键，更新或删除表中的特定行很困难，因为没有安全的方法保证只涉及相关的行。
• MySQL在执行匹配时默认不区分大小写。根据MySQL的配置方式，搜索可以是区分大小写的。
• 可移植的：能运行在多个系统上的代码
• 可伸缩性：能够适应不断增加的工作量而不失败。

基本知识

• 两种变量：
  • primitive主数据类型
  • 引用变量（其值位于堆上）【相当于遥控器】
• 对象：状态（实例变量 instance varible)、行为(方法 method)
• 主要在类中使用封装 (set 函数) 来隐藏数据
  • 将实例变量标记为private, 将get/set方法标记为public
• 实例变量永远都会有默认值，但局部变量未被初始化 使用时被给出error，即其没有默认值
  • integers 0
  • floating 0.0
  • boolean false
  • reference null
• 变量的比较：
  • 使用==比较两个primitive 主数据类型，或者判断两个号|用是否引用同一个对象。
  • 使用 equals()来判断两个对象是否在意义上相等。（像是两个 String对像是否带有相同的字节组合）

构造器与垃圾收集器

栈与堆

• 对象在堆上，类中的实例变量（实质上是对象的一部分）自然也在堆上
• 局部变量和方法调用在栈上，对象引用变量与primitive主数据类型变量都是放在栈上

构造函数

• 当类中手动写了一个带有参数的构造函数时，编译器不会主动帮你写一个无参数的构造函数，因此需要自己写！！
• 使用this()从某个构造函数调用同一个类的另外一个构造函数。this()只能用在构造函数中，且必须是第一行语句。super()与this()不能兼得。

• 、

20200713 15:01 结

• 关键词：自动化软件测试，模糊化，软件安全
• 目的：作为一个survey，围绕模糊化，给它下定义，总结对软件测试提出的模糊化方面的改进，发掘有哪些创新点
• 领域： 软件测试，模糊化

基础知识

定义

• 模糊化是什么？
  • 使用生成的输入（输入存在语义和语法错误）重复运行一个项目。
• 目前模糊化有哪些问题？
  • 一些fuzzer工具的源代码和手册实际达不到描述的那样
  • 不同fuzzer工具使用的术语各大相同
• Fuzzing定义
  • 从fuzz输入空间生成样例测试Program，并突出PUT(Program Under Test)期望的输入空间
• Fuzz Testing定义
  • 使用fuzzing技术去测试看是否PUT违背安全政策
  • 目的：找出program中影响安全的bugs
• Fuzzer定义
  • 在一个PUT上执行fuzzing testing的Program
• Fuzz Campaign
  • 针对一条特定安全政策，一个fuzzer在PUT上的一个特定的执行，相当于专门针对哪个安全，制作出一些sample去用fuzzer执行。
• Bug Oracle
  • 作为fuzzer的一部分Program，检测给定的PUT执行是否违反特定安全政策
• Fuzz Configuration
  • Fuzz算法的参数配置，依赖于特定的fuzz algorithm
• 设计测试工具的时候，一定先熟悉源代码和PUT的相关知识！！！

Fuzz Testing 算法

• 有两个部分：对配置进行预处理；迭代（包括Schedule,InputGen,InputEval,ConfUpdate,Continue）
  • PREPROCESS：执行大量操作，比如插入一些功能性代码到PUTs中，或是检测种子文件（产生测试样例）的执行速度
  • 第二部分的迭代的流程：先选择一个fuzz配置；根据配置中的参数生成测试样例；用测试样例和oracle bug检测是否违背安全政策（这个应该可以自己规定），这时可以得到execinfos，这大概是为了变动配置，为了之后能选取到更具有代表性的配置去生成测试样例；根据execinfos,改变fuzz配置；最后判断fuzz配置是否进行下一轮的迭代。

Fuzzer的分类

• 根据在每次fuzz run的时候fuzzer观察到的东西多少，以下只是安全专家的一致认同，在实际使用的时候，三者的区别不太明显。

• 黑盒fuzzer

  • 只能看到PUT输入和输出的表现，有一些还考虑输入的结构信息
• 白盒fuzzer
  • 可以观察到PUT的内部信息以及执行过程中的收集到的信息
• 灰盒fuzzer
  • 可以观察到一部分PUT的内部信息和它的执行，但是不能得到PUT完成的语义，且只能对PUT执行轻量级的分析和对执行收集动态信息。即收集一些近似信息

PREPROCESS

• 预处理包括对PUT做一些性能监控（灰盒、白盒都能去PUT中获取一些反馈信息）[对PUT进行插桩]，去除冗余的配置（像种子选择），修剪种子，生成驱动应用。

Instrumentation

• 白盒、灰盒中用来收集最有价值反馈的一种方法，代码插桩（在被测程序中插入完成相应工作的代码，即代码插桩技术，来获取程序中可执行语句被执行（即被覆盖）的情况）
• 分为static instrumentation和dynamic instrumentation，前者一般在源代码的编译阶段执行，后者一般在运行阶段执行。

Execution Feedback

• 灰盒fuzzers将执行反馈作为输入去优化测试样例，AFL等文章计算分支覆盖率作为反馈内容，但容易发生分支冲突，对此CollAFL提出相应解决方法。

In-Memory Fuzzing

• 为了最小化执行开销，每次fuzz迭代只fuzz一部分的PUT,program会保留PUT的快照，下次fuzz新的测试样例时需要恢复memory快照。这种快照可以避免执行不必要的启动代码。
• in-memiry API fuzzing通过一个函数而不是每次迭代恢复PUT的状态，这种方式尽管有效，但是找到的bugs却不完整，因为可能调用不到这种函数（我猜是函数名生成有问题？？）

Thread Scheduling

• 随机调度线程对找到race condition bugs很有效。

Seed Selection

• 希望选取最小的种子集合最大化覆盖率（如节点覆盖率）
• 覆盖率评价指标：
  • branch coverage（计算分支的执行次数），当测试样例在分支执行次数上的数量级不同时才认为它们是不同的
  • the number of executed instructions,executed branches,and unique basic block。希望将最长的执行路径的测试样例增加到minset中。

Seed Trimming

• 在preprocess中执行，或作为CONFUPDATE的一部分

• 在AFL中只要修改过的seed能够达到和原先种子一样的覆盖率，就修剪掉原先种子。

• [177]发现size小的种子没啥用

Preparing a Driver Application

• 给fuzzer一开始的时候准备一个驱动器（这里不太理解）

SCHEDULING

• 选择一个fuzz 配置为下轮fuzz迭代，不同的fuzzer类型具有不同的配置。这里主要的研究点是提出创新性的scheduling算法。

The Fuzz Cofiguration Scheduling (FCS) Problem

• 挑选一个可能产生最好结果的配置（评判可能依据 find the most number of unique bugs[unique bugs不知道咋翻译], maximize the coverage]。在挑选的时候考虑explore（关于每个配置获取更为准确的信息）和exploit（获取好的结果），做这两者的trade-off。

Black-box FCS Algorithms

• 黑盒用到的反馈信息：crashes和bug的数量毕竟执行时间
• [225]提炼数学模型，WCCP/UW，由于反馈信息会随着配置结果变差，因此选择一些配置不会导致反馈decay。为了将crashes或bugs / time来修改反馈信息，目的是为了能更快速地进行配置（感觉是把time因素考虑进去）。

Grey-box FCS Algorithms

• 灰盒用到的反馈信息：黑盒能用到的，达到的覆盖率等等
• AFL认为执行最快，input最少的是fit

• AFLFast在AFL基础上做了三点改进

  • 增加两条重要准则：
    • AFLFast喜欢被选中最少的配置
    • AFLFast喜欢最少选择的路径
  • AFLFast在AFL增加了优先级，替代AFL中的圆形选择
  • AFLFast每个配置被选中次数是动态改变的

• AFLGo修改了AFLFast优先级的特征，目的是为了找到特定的程序位置。

INPUT GENERATION

• 分为generation-based和mutation-based，前者是基于model的，后者是通过mutate seed。

Model-based (Generation-based) Fuzzers

• 预定义或用户提供的模型
• 推断模型可能发生在PREPROCESS阶段也可能在CONFUPDATE阶段
  • 在PREPROCESS阶段，在PUT中搜找可用的数据（如文字），去预测合适的输出
  • 在CONFUPDATE阶段，每次迭代更新model
• 编译器模型（不太能理解这个模型）
  • 解析特定的文件格式

Model-less (Mutation-based) Fuzzers

• 需要seed-based输入生成和白盒输入生成。
• Bit-flipping：翻转固定/不固定数量bit位，用mutation ratio决定翻转多少数量的bit位。因此，找到一个合适的mutation ratio数值至关重要。
• Arithmetic Mutation：将选择的字节序列视为一个整数，对整数进行处理（不太能理解）
• Block-based Mutation：以block为单位，进行mutation
• Dictionary-based Mutation：对具体的字符（数值）进行mutation（不太能理解）

White-box Fuzzers

• 先使用白盒程序分析找到PUT的信息，用这信息去进行黑盒or灰盒fuzzing。

• Dynamic symbolic execution：比灰盒和黑盒慢很多，因为它需要对PUT的每条指令进行插桩和分析，这方面的研究都聚集在如何减少它的代价方面。

• Guided Fuzzing：先对PUT进行分析（静态or动态分析）来获取有用的信息；再利用这个信息去生成test case。这上面的研究一方面需要减少分析产生的代价。

• PUT Mutation：不重要。。

INPUT EVALUATION

Bug Oracles

• 有三个方面的侦测：内存安全问题（是否访问到不安全的内存、控制流的完整性[啥意思]）、访问到未被定义的行为（如编译器不同，程序猿只考虑了某些编译器情况下可行，但有些不可行却忽略了）、输入的合法性（比如SQL访问可能对数据库引擎存在一些破坏）

Execution Optimizations

• 由于迭代需要每次都初始化PUT进程，需要耗费大量的时间，对此，AFL提供了一个fork-server去让迭代去从进行初始化好的进行进程中fork一下。

Triage

• 分析和报告导致违反政策（感觉就是不安全的）的进程，分为三步：去重复、优先级、测试样例最小化。

Deduplication

• 去重复：若该test case返回的Bug已经被以前的test case找到了，这个test case就不要了。能得到test case集合，该集合中每个test case都能触发唯一的bug。去重复有三种主要的实现方式：
  • stack backtrace hashing
    • 记录了crash时的stack backtrace(如：main → d → c → b → a → foo )，当其他crash时的stack backtrace的后五个也是这个时候，认为他们重复, 这是major hash。而minor hash还考虑到line number（感觉是数量）。但这样做事基于一种假设，即相似的crash是由相似的bugs引起的，但这假设未被验证，且能举出反例。
  • coverage-based deduplication
    • 在PUT中插桩记录PUT每次执行的edge覆盖率，根据这个信息选取seeds，AFL认为当crash覆盖到之前未见到的edge或者未覆盖到之前在所有其他crashes中都覆盖到的edge时，认为该crash是唯一的。
  • semantics-aware deduplication
    • 从每个crash处反向分析，找到那个function，根据function来对crashes进行分类。(怎么那么奇怪)

###

Prioritization and Exploitability

• 根据一个crash的可利用性来划分优先级。Microsoft’s !exploitable的优先级划分： EXPLOITABLE > PROBABLY_EXPLOITABLE > UNKNOWN >

  NOT_LIKELY_EXPLOITABLE,

Test case minimization

• 利用bug oracle进行test case 最小化。许多fuzzers都针对自己特定的情况选用test case最小化算法。

CONFIGURATION UPDATING

• 可用来区别是白盒fuzzer、黑盒fuzzer、灰盒fuzzer。由于黑盒只能用到Oracle bug(不能得到PUT的内部信息)大部分Conf都不被修改。

Evolutionary Seed Pool Update

• 灰盒fuzzer大多基于遗传算法进行展开，EA-based fuzzers大多数使用node或者Branch覆盖度作为fitness function.[后面举例没仔细看]

Maintaining a Minset

• 赋予favorable fuzzing conf以高的被选择进行fuzzing的权重。思想是：需要少的test case最大化coverage评价指标。

​

Links:

• paper: https://ieeexplore.ieee.org/abstract/document/8863940

Testing Database Engines via Pivoted Query Synthesis论文

主要内容

• 随机生成table和rows
• 从每个表随机生成一行
• 根据选择的rows随机生成表达式并评估结果
• 修改表达式 直到返回真

领域

• 检测logic bug，logic bug即是否返回正常的行

研究常用的方法

• 差异性测试，不适用于所有DBMS

  

各项性能指标

• 观察是否返回 随机生成的row

缺点

• 不适用于大数据集
• 可能只能做where里面的AST树

扩展知识点

• AST树
• 差异性比较

Detecting Optimization Bugs in Database Engines via Non-Optimizing Reference Engine Construction论文

主要内容

• 不正常的优化可能会导致logic bug

• 核心：重写DBMS不能优化的潜在随机生成优化的query

• 让DBMS不做优化，做全表的扫描

  

  • 左边是原本数据库会优化的，右边是数据库不会优化的。

• 

Ternary Logic Partitioning: Detecting Logic Bugs in Database Management Systems

主要内容

• query分区，将一条给定原始的query，分成多份更复杂的queries，每个部分都计算结果的一部分。

• 三元逻辑分区：

  • 基于一个布尔谓词p计算成True,False,NULL的观察

• 

主要内容

• 自动给学生的sql query打分，局部打分，通过判断错误严重的程度。

• 采用 weighted equivalence edit distance metric，找到最小的编辑序列，能将原始错误的sql query转为正确的query。

• 使用query规范化规则针对语法和语义进行规划

  • 语法，如将Not(A>B) 替换为A<=B; 将操作构建一棵flattened tree
  • 语义，将query中主键上的distinct移除，将query中冗余的关系移除。

• Flattened Tree Structure

  

  • 将query中有连接关系的都flatten一下，转化为等价形式。
  • 针对flattened tree，谓词/投影/聚类操作都作为一棵棵子树

• 计算规范化的编辑距离

  • 对于每个组件（子树）分别计算编辑距离，然后找到每个quert的带权距离。Σc∈componentsWc ∗ Ec

• 根据编辑距离给分

领域

• 指出错误sql query错在那个部分，也就是做最小的改动，能让sql query变成正确的。

研究常用的方法

• XData通过比较正确query和学生query得到的结果，对学生 sql query进行二分类，即判别正确or错误，但太简单了，想得到更细致的。
• 根据正确query和学生query返回结果交集所占正确结果的比例，但有可能因为一个很小的错误得出的结果很差，导致分数低。
• 学生的sql query需要做多少个变化才能和正确的sql等价，但许多具有语义差异的sql在返回的结果却没什么差异。（本文）针对此，使用大量query规范化技巧移除学生和正确的queries的不相关的语法和语义差别。但是需要给出多个正确的queries，将学生query与其相比较，选出匹配度最高的query。这个问题可以抽象为图中找最短路径，提出一个贪心启发性技巧。

问题

• 基于规范化编辑距离的给分有可能是不公平的，在规范化部分还存在一些问题。

实验部分和讨论部分

• 随机创建一对不正确的学生queries，a和b，让两个志愿者对每对queries分类，第一类是a queriy的分高，第二类是b query的分高，第三类是a,b query的分数一样高。

• potentially an infinite number of edit options are possible

对负载生成的启发点

SQL QUERY 规范化

• B. Chandra, M. Joseph, B. Radhakrishnan, S. Acharya, and S. Sudarshan.

  Partial marking for automated grading of SQL queries. PVLDB (Demo),

  9(13):1541–1544, 2016.

Source Code

• https://www.cse.iitb.ac.in/infolab/xdata
• https://gitlab.com/xdata/xdata-web/-/tree/developer/XDataGrading/src