Linux内核定时器并发错误检测
CSTR:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

TP306

基金项目:

国家重点研发计划(2022YFE0113200); 国家自然科学基金重点项目(U21A20464)


Detection of Timer Concurrency Bug in Linux Kernel
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    定时器是操作系统延迟任务调度与执行的驱动器, 具有运行在原子上下文和异步执行的特性, 可以在任何时刻与不同的线程并发执行, 如果开发人员不能考虑到所有多线程交错的场景, 则可能引入多种类型的并发错误, 对操作系统安全产生严重威胁. 定时器并发错误不仅涉及多线程交错, 还涉及定时器处理程序的延迟执行与重复调度, 比普通的并发错误更难发现, 目前还没有工具可以有效地检测此类错误. 总结3种定时器并发错误类型, 即定时器睡眠错误、定时器死锁错误和僵尸定时器错误. 为有效地对错误进行检测, 首先通过指针分析, 提取内核中所有与定时器有关的功能模块, 避免对无关代码进行分析提高检测效率; 然后构建上下文敏感、路径敏感和流敏感的过程间控制流图, 为后续分析奠定基础; 最后综合应用函数调用图遍历、锁集分析、指向分析、控制流分析等静态分析技术, 设计针对3种定时器并发错误的检测算法. 为评估算法的有效性, 在Linux 5.15内核中共发现了328个真实定时器并发错误, 向Linux内核社区提交了个56个补丁, 截至目前, 49个补丁已经合并到Linux内核主线, 295个错误被确认和修复, 申请了14个CVE编号, 说明了所提方法的有效性. 最后通过对比实验对算法的性能、漏报与误报情况进行了系统分析, 并总结3种定时器并发错误的修复方法.

    Abstract:

    A timer is used to schedule and execute delayed tasks in an operating system. It operates asynchronously in an atomic context and can execute concurrently with different threads at any time. If developers fail to account for all possible scenarios of multithread interleaving, various types of concurrency bugs may be introduced, posing a serious threat to the security of the operating system. Timer concurrency bugs are more difficult to detect than typical concurrency bugs because they involve not only multithread interleaving but also the delayed and repeated scheduling of timer handlers. Currently, there are no tools that can effectively detect such bugs. In this study, three types of timer concurrency bugs are summarized: sleeping timer bugs, timer deadlock bugs, and zombie timer bugs. To enhance detection efficiency, firstly, all timer-related code is extracted through pointer analysis, reducing unnecessary analysis overhead. A context-sensitive, path-sensitive, and flow-sensitive interprocedural control flow graph is then constructed to provide a foundation for subsequence analysis. Based on static analysis techniques, including call graph traversal, lockset analysis, points-to analysis, and control flow analysis, three detection algorithms are designed to identify the different types of timer concurrency bugs. To evaluate the effectiveness of the proposed algorithm, they are applied to the Linux 5.15 kernel, where 328 real-world timer concurrency bugs are detected. A total of 56 patches are submitted to the Linux kernel community, with 49 patches merged into the mainline kernel, 295 bugs confirmed and fixed, and 14 CVE identifiers assigned. These results demonstrate the effectiveness of the proposed method. Finally, a systematic analysis of performance, false positives, and false negatives is conducted through comparative experiments, and methods for repairing the three types of bugs are summarized.

    参考文献
    相似文献
    引证文献
引用本文

周多明,马麟,周亚金. Linux内核定时器并发错误检测.软件学报,,():1-30

复制
相关视频

分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2023-08-16
  • 最后修改日期:2024-03-04
  • 录用日期:
  • 在线发布日期: 2025-05-14
  • 出版日期:
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号