I/O dependent idempotence bugs in intermittent systems
I/O dependent idempotence bugs in intermittent systems
复制标题
DOI：
10.1145/3360609
复制
发表时间：
2019-10
影响因子：
--
通讯作者：
Milijana Surbatovich;Limin Jia;Brandon Lucia
中科院分区：
文献类型：
--
作者：
Milijana Surbatovich;Limin Jia;Brandon Lucia
间歇供电的能量收集设备从其环境中收集能量，并且必须在有能量可用时间歇运行。此类设备的运行时系统通常依赖于检查点或重做日志来保存电源周期之间的执行状态，从而导致在重新启动时重新执行任意代码区域。任何非幂等的程序行为（每次执行时都可能发生变化的行为）都可能导致不正确的结果。这项工作调查了由重复I/O操作引起的非幂等行为，这是以前的工作没有解决的。如果这些操作影响控制语句或内存更新的地址，它们可能导致程序在重新执行时采用不同的路径或写入不同的内存位置，从而导致内存状态不一致。我们提供了输入相关幂等性错误的第一个特征，并开发了IBIS-S（用于在编译时检测此类错误的程序分析工具）和IBIS-D（用于在运行时检测错误的动态信息流跟踪器）。这些工具使用污染传播来确定输入的范围。IBIS-S搜索导致内存更新不一致的代码模式，而IBIS-D则检测具体的内存不一致。我们在嵌入式系统驱动程序和应用程序上评估IBIS。IBIS可以检测与I/ o相关的幂等性错误，给出很少（IBIS- s）或没有（IBIS- d）误报，并提供可操作的错误报告。这些错误在传感器驱动的应用程序中很常见，并且无法通过现有的间歇性系统修复。
Intermittently-powered, energy-harvesting devices operate on energy collected from their environment and must operate intermittently as energy is available. Runtime systems for such devices often rely on checkpoints or redo-logs to save execution state between power cycles, causing arbitrary code regions to re-execute on reboot. Any non-idempotent program behavior—behavior that can change on each execution—can lead to incorrect results. This work investigates non-idempotent behavior caused by repeating I/O operations, not addressed by prior work. If such operations affect a control statement or address of a memory update, they can cause programs to take different paths or write to different memory locations on re-executions, resulting in inconsistent memory states. We provide the first characterization of input-dependent idempotence bugs and develop IBIS-S, a program analysis tool for detecting such bugs at compile time, and IBIS-D, a dynamic information flow tracker to detect bugs at runtime. These tools use taint propagation to determine the reach of input. IBIS-S searches for code patterns leading to inconsistent memory updates, while IBIS-D detects concrete memory inconsistencies. We evaluate IBIS on embedded system drivers and applications. IBIS can detect I/O-dependent idempotence bugs, giving few (IBIS-S) or no (IBIS-D) false positives and providing actionable bug reports. These bugs are common in sensor-driven applications and are not fixed by existing intermittent systems.