QL: Object-Oriented Queries on Relational Data

是什么

QL: Object-Oriented Queries on Relational Data 提出：QL：关系数据上的面向对象查询。

日常类比：像用 SQL 查代码结构图，找危险模式。

读论文时先抓「威胁模型/假设→核心构造→复杂度/开销」三件事。

为什么重要

GitHub Advanced Security
静态分析产品化
对照污点动态
供应链审计

核心要点

问题设定：作者要解决什么不可能三角（安全/性能/易用）。
关键技巧：一个构造或定理把难题拆成可实现步骤。
安全假设：信任根、敌手能力、失败概率。
工程映射：开源库与 RFC 如何落地论文思想。
局限：已知攻击面、参数选取、未来工作。

实践案例

案例 1：画威胁模型表

列：资产、敌手、能力、目标；对照论文假设勾选覆盖项。

案例 2：找开源实现

# 搜索论文标题 + library 名称，读 README 的 security note

案例 3：与邻居论文对照

阅读 newsome-taintcheck-2005，画时间线：哪篇解决 setup/性能/证明长度。

案例 4：面试复述

用「类比 + 三要点」在 2 分钟内讲清；准备一条「为什么不用更简单方案」。

案例 5：与双千 atlas 交叉阅读

在 papers-atlas 找同子类 1 篇，对比实践案例是否覆盖实验/参数/失败模式。

踩过的坑

把理想模型当产品默认：论文参数在工业界常被放宽。
忽略组合开销：多个原语组合时安全界不是简单相加。
误读实验规模：小数据集上的 ε 不可直接外推。
混淆相似缩写：如 DP/LDP、SNARK/STARK 场景不同。
行数与模板：交付前用 quality-gate 扫一遍。

适用 vs 不适用场景

适用：

安全/系统/architecture 面试深挖
选型隐私或密码组件前的理论扫盲
读源码前的概念地图

不适用：

不做威胁建模直接上生产
替代官方标准文本（FIPS/RFC）
数学证明细节（请读原文附录）

历史小故事（可跳过）

论文常是多年社区实践的第一次形式化。
标准机构（NIST/IETF）往往在论文后收敛算法名。
开源实现与论文版本存在参数漂移，以 release 为准。
近年与 ML、TEE、区块链场景强交叉。

学到什么

安全方案先问威胁模型，再问漂亮数学。
工程落地看常量与实现漏洞，不只看渐近复杂度。
论文链式阅读比单篇精读更高效。
与站内 neighbors 互链能形成可复习的知识图。
QL 的谓词系统让数据流分析可组合：一个库查询可复用于多个规则。
静态分析的假阳性不可避免，关键是把误报率控制在工程团队可接受范围。

核心算法细节

QL 谓词系统与关系型 OOP

QL 是一种面向对象的查询语言，底层编译为 Datalog 风格的关系型求值。每个类 (class) 对应一个谓词集合，继承意味着子类谓词对父类成立。例如：

class SqlQuery extends MethodAccess {
  SqlQuery() {
    this.getMethod().getName() = "query"
  }
  Expr getArgument() { result = this.getArgument(0) }
}

数据流追踪：source-sink 分析

CodeQL 的污点追踪 (TaintTracking) 分三步：

定义 source：用户可控输入点（HTTP 参数、文件读取等）
定义 sink：危险操作点（SQL 执行、命令拼接等）
追踪路径：通过局部数据流 + 跨函数摘要推断中间传播链

import semmle.code.java.dataflow.TaintTracking
import DataFlow::PathGraph

class SqlInjectionConfig extends TaintTracking::Configuration {
  SqlInjectionConfig() { this = "SqlInjectionConfig" }
  override predicate isSource(DataFlow::Node src) {
    src instanceof RemoteFlowSource
  }
  override predicate isSink(DataFlow::Node sink) {
    sink.asExpr() instanceof SqlQuery
  }
}

from SqlInjectionConfig cfg, DataFlow::PathNode src, DataFlow::PathNode sink
where cfg.hasFlowPath(src, sink)
select sink, src, sink, "SQL injection via $@.", src, "user input"

控制流图与调用图构建

QL 在代码提取阶段（codeql database create）将源代码解析为关系型快照，包含：

AST 关系：语句、表达式、类型层次
CFG 关系：ControlFlow::Node 边及 BasicBlock
调用图：虚拟调用（virtual dispatch）通过类型分析解析

复杂度分析

Datalog 求值的时间复杂度与关系大小正相关。对大型项目（百万行代码）：

提取阶段：与编译时间相当（1–10 分钟）
查询阶段：简单谓词 <1 分钟，全程序流分析 5–30 分钟
增量分析：仅重算受修改影响的关系，CI 中常用

工程实现要点

数据库版本锁定：CodeQL 数据库与 CLI 版本须匹配，升级 CLI 须重建数据库
查询包管理：用 qlpack.yml 声明依赖，避免手动拷贝查询文件
CI 集成：codeql-action 支持 PR 审查自动扫描，结果以 SARIF 格式上传
自定义规则发布：将查询打包为 CodeQL pack 推送到 GitHub Packages 供团队复用
性能调优：对慢查询用 --evaluator-log 分析求值热点，必要时加 pragma[noinline]

关联

newsome-taintcheck-2005 —— 同路线前后文
cadar-klee-2008 —— 同路线前后文

维护备注

引用格式保持单引号包裹 来源 字段。

反向链接

bohme-aflfast-2016 —— AFLFast — 灰盒 Fuzz 的马尔可夫调度
cadar-klee-2008 —— KLEE — 符号执行自动生成高覆盖测试
newsome-taintcheck-2005 —— Dynamic Taint Analysis for Automatic Detection, Analysis, and Signature Generation of Exploits on Commodity Software