摘要: 无线信号之间的干扰阻碍了信号的并发传输,降低了无线网络的吞吐量.链路调度是提高无线网络吞吐量、减少信号传输延迟的一种有效方法.因为SINR(Signal to Interference plus Noise Ratio)模型准确地描述了无线信号传播的固有特性,能够真实反映无线信号之间的干扰,本文提出了一种在动态无线网络中基于SINR模型的常数近似因子的在线分布式链路调度算法(简称OLD_LS).在线的意思是指,在算法执行的过程中任意节点可以随时加入网络,也可以随时离开网络.节点任意加入网络或者从网络中离开体现了无线网络的动态变化的特性.OLD_LS算法把网络区域划分为多个正六边形,局部化SINR模型的全局干扰.本文设计了动态网络下的领导者选举算法(简称LE),只要网络节点的动态变化速率小于1/ε,LE就可以在O(logn+logR)时间复杂度内以高概率选举出领导者.其中, 常数ε满足ε≤5(1-21-α/2)/6,α表示路径损耗指数,n是网络节点的规模,R是最长链路的长度.据我们所知,本文提出的算法是第一个用于动态无线网络的在线分布式链路调度算法.
摘要: 作为Serverless架构的一种典型形态,函数即服务(Function as a Service,简称FaaS)架构将业务抽象为细粒度的函数,并且提供弹性的自动伸缩等自动化运维功能,能够大幅降低运维成本.当前许多在线服务系统中的一些高并发、高可用、灵活多变的业务(如支付、红包等)都已经迁移到了FaaS平台上,但是大量传统单体应用还是难以利用FaaS架构的优势.针对这一问题,本文提出了一种基于动态和静态分析的单体应用FaaS改造方法.该方法针对指定的单体应用API,通过动态分析和静态分析相结合的方式识别并剥离其实现代码和依赖,然后按照函数模板完成代码重构.针对函数在高并发场景下的冷启动问题,该方法利用基于IO多路复用的主从多线程Reactor模型优化了函数模板,提高了单个函数实例的并发处理能力.基于该方法我们实现了针对Java语言的原型工具Codext,在开源Serverless平台OpenFaaS上面向4个开源单体系统进行了实验验证.
摘要: 随着数字信息技术的普及,密文可逆信息隐藏(Reversible Data Hiding in Encrypted Images,RDHEI)逐渐成为云存储中隐私保护的研究热点.RDHEI作为一种能在密文中嵌入额外信息,并正确提取嵌入信息和无损恢复原始图像的技术,受到研究者的广泛关注.为了能在加密图像中嵌入充足的额外信息,本文提出了一种自适应编码的高容量RDHEI算法.首先,计算原始图像不同预测误差的出现概率并自适应的生成哈夫曼编码;然后,利用流密码加密原始图像,根据像素预测误差对应的哈夫曼码字对加密后像素进行标记;最后,以位替换方式将信息嵌入到已标记像素的预留空间中.经实验验证,本文算法在正确提取嵌入信息的同时,无损地恢复了原始图像.与同类算法相比,本文算法充分利用了图像本身的纹理特性,有效地提高了图像嵌入率.在UCID、BOSSBase和BOWS-2三个图像集上,本文算法的平均嵌入率达到3.162bpp、3.917bpp以及3.775bpp,与当前性能最佳算法相比提升了0.263bpp、0.292bpp以及0.280bpp.
摘要: 近年来,传统磁记录的存储密度增长已经达到极限,为了满足快速增长的数据容量需求,多种新型存储技术不断涌现,其中瓦记录(Shingled Magnetic Recording,简写为SMR)技术已实现商业化,在企业实际应用.但是,由于瓦记录磁盘的叠瓦式结构,磁盘在随机写入时会引起写放大,造成磁盘性能下降.这一问题在部署传统的高可靠存储方案(如RAID5)时会变得更加严重,原因在于是校验数据更新频率很高,磁盘内出现大量的随机写请求.本文发现瓦记录内部其实存在具有原位更新能力的"可覆盖写磁道"(Free Track),因此基于"可覆盖写磁道",提出了一种专门针对瓦记录盘的高可靠数据存储方法——FT-RAID,以替代经典的RAID5方法,实现一个廉价、大容量、高可靠的存储系统.FT-RAID包含两个部分:"可覆盖写磁道映射"(FT-Mapping)和"可覆盖写磁道缓冲区"(FT-Buffer).FT-Mapping实现了一种瓦记录友好的RAID映射方式,将频繁更新的校验块数据映射至"可覆盖写磁道";FT-Buffer实现了一种瓦记录友好的两层缓冲区结构,上层确保了热数据能够原位更新,下层提高了缓冲区的容量.基于真实企业I/O访问记录的的实验表明,与传统RAID5相比,FT-RAID能减少80.4%的写放大率,显著提高存储系统整体性能.
摘要: 自适应隐写是图像隐写方向的研究热点,它通过有效地设计隐写失真函数,自适应地将秘密信息隐藏在图像复杂的纹理区域,具有很强的隐蔽性.近年来,基于生成对抗网络的隐写失真函数设计研究在空域灰度图像上已经取得了突破性的进展,但是目前还没有针对空域彩色图像的研究.与灰度图像相比,彩色图像隐写需要考虑保护RGB通道间相关性,同时合理地分配RGB三个通道的嵌密容量.本文设计了一个基于生成对抗网络设计空域彩色图像隐写失真函数的框架CIS-GAN(color image steganography based on generative adversarial network),生成器网络采用两个U-Net子网络结构,第一个U-Net子网络生成修改概率矩阵,第二个U-Net子网络进行正负向修改概率调节,有效地降低对彩色图像通道相关性的破坏.针对彩色图像载体,修改灰度图像隐写分析器作为网络的对抗部分.在生成器损失函数中对彩色图像三个通道总的隐写容量进行控制,生成器能够自动学习分配三个通道嵌密容量.实验结果表明,与现有彩色图像隐写失真函数设计方法相比,本文提出的网络结构能够更好地抵抗彩色图像隐写分析器的检测.
摘要: Data race is a major source of concurrency bugs. Dynamic data race detection tools (e.g., FastTrack) monitor the execu-tions of a program to report data races occurring in runtime. However, such tools incur significant overhead that slows down and perturbs executions. To address the issue, the state-of-the-art dynamic data race detection tools (e.g., LiteRace) ap-ply sampling techniques to selectively monitor memory access-es. Although they reduce overhead, they also miss many data races as confirmed by existing studies. Thus, practitioners face a dilemma on whether to use FastTrack, which detects more data races but is much slower, or LiteRace, which is faster but detects less data races. In this paper, we propose a new sam-pling approach to address the major limitations of current sampling techniques, which ignore the facts that a data race involves two threads and a program under testing is repeatedly executed. We develop a tool called AtexRace to sample memory accesses across both threads and executions. By selectively monitoring the pairs of memory accesses that have not been frequently observed in current and previous executions, AtexRace detects as many data races as FastTrack at a cost as low as LiteRace. We have compared AtexRace against FastTrack and LiteRace on both Parsec benchmark suite and a large-scale real-world MySQL Server with 223 test cases. The experiments confirm that AtexRace can be a replacement of FastTrack and LiteRace.
摘要: It is difficult to fix atomicity violations correctly. Existing gate lock algorithm (GLA) simply inserts gate locks to serialize exe-cutions, which may introduce performance bugs and deadlocks. Synthesized context-aware gate locks (by Grail) require complex source code synthesis. We propose ?Fixer to adaptively fix ato-micity violations. It firstly analyses the lock acquisitions of an atomicity violation. Then it either adjusts the existing lock scope or inserts a gate lock. The former addresses cases where some locks are used but fail to provide atomic accesses. For the latter, it infers the visibility (being global or a field of a class/struct) of the gate lock such that the lock only protects related accesses. For both cases, ?Fixer further eliminates new lock orders to avoid introducing deadlocks. Of course, ?Fixer can produce both kinds of fixes on atomicity violations with locks. The experi-mental results on 15 previously used atomicity violations show that: ?Fixer correctly fixed all 15 atomicity violations without introducing deadlocks. However, GLA and Grail both intro-duced 5 deadlocks. HFix (that only targets on fixing certain types of atomicity violations) only fixed 2 atomicity violations and introduced 4 deadlocks. ?Fixer also provides an alternative way to insert gate locks (by inserting gate locks with proper visibility) considering fix acceptance.
摘要: Numerical instability is a well-known problem that may cause serious runtime failures. This paper discusses the reason of instability in software development process, and presents a toolchain that not only detects the potential instability in software, but also diagnoses the reason for such instability. We classify the reason of instability into two categories. When it is introduced by software requirements, we call the instability caused by problem. In this case, it cannot be avoided by improving software development, but requires inspecting the requirements, especially the underlying mathematical properties. Otherwise, we call the instability caused by practice. We design our toolchain as 4 loosely-coupled tools, which combine stochastic arithmetic with infinite-precision testing. Each tool in our toolchain can be configured with different strategies according to the properties of the analyzed software. We evaluate our toolchain on subjects from literature. The results show that it effectively detects and separates the instabilities caused by problems from others. We also conduct an evaluation on the latest version of GNU Scientific Library, and the toolchain finds a few real bugs in the well-maintained and widely deployed numerical library. With the help of our toolchain, we report the details and fixing advices to the GSL buglist.
摘要: Code contributions in Free/Libre and Open Source Software projects are controlled to maintain high-quality of software. Alternatives to patch-based code contribution tools such as mailing lists and issue trackers have been developed with the pull request systems being the most visible and widely available on GitHub. Is the code contribution process more effective with pull request systems? To answer that, we quantify the effectiveness via the rates contributions are accepted and ignored, via the time until the first response and final resolution and via the numbers of contributions. To control for the latent variables, our study includes a project that migrated from an issue tracker to the GitHub pull request system and a comparison between projects using mailing lists and pull request systems. Our results show pull request systems to be associated with reduced review times and larger numbers of contributions. However, not all the comparisons indicate substantially better accept or ignore rates in pull request systems. These variations may be most simply explained by the differences in contribution practices the projects employ and may be less affected by the type of tool. Our results clarify the importance of understanding the role of tools in effective management of the broad network of potential contributors and may lead to strategies and practices making the code contribution more satisfying and efficient from both contributors' and maintainers' perspectives.
摘要: Code contributions in Free/Libre and Open Source Software projects are controlled to maintain high-quality of software. Alternatives to patch-based code contribution tools such as mailing lists and issue trackers have been developed with the pull request systems being the most visible and widely available on GitHub. Is the code contribution process more effective with pull request systems? To answer that, we quantify the effectiveness via the rates contributions are accepted and ignored, via the time until the first response and final resolution and via the numbers of contributions. To control for the latent variables, our study includes a project that migrated from an issue tracker to the GitHub pull request system and a comparison between projects using mailing lists and pull request systems. Our results show pull request systems to be associated with reduced review times and larger numbers of contributions. However, not all the comparisons indicate substantially better accept or ignore rates in pull request systems. These variations may be most simply explained by the differences in contribution practices the projects employ and may be less affected by the type of tool. Our results clarify the importance of understanding the role of tools in effective management of the broad network of potential contributors and may lead to strategies and practices making the code contribution more satisfying and efficient from both contributors' and maintainers' perspectives.
摘要: Software should behave correctly even in adverse conditions. Particularly, we study the problem of automated validation of crash consistency, i.e., file system data safety when systems crash. Existing work requires non-trivial manual efforts of specifying checking scripts and workloads, which is an obstacle for software developers. Therefore, we propose C3, a novel approach that makes crash consistency validation as easy as pressing a single button. With a program and an input, C3 automatically reports inconsistent crash sites. C3 not only exempts developers from the need of writing crash site checking scripts (by an algorithm that computes editing distance between file system snapshots) but also reduces the reliance on dedicated workloads (by test amplification). We implemented C3 as an open-source tool. With C3, we found 14 bugs in open-source software that have severe consequences at crash and 11 of them were previously unknown to the developers, including in highly mature software (e.g., GNU zip and GNU coreutils sort) and popular ones being actively developed (e.g., Adobe Brackets and TeXstudio).
摘要: Internet 流量模型对网络性能管理、QoS、准入控制等都有很重要的意义和作用.首先总结了现阶段已发现的主要网络流量的特性及相关度量参数,概要地介绍网络流量建模的意义和分类,然后按照“传统-自相似-流量建模的新发展”这3 个阶段阐述网络流量建模的发展历程与最新的研究成果,最后针对目前网络流量建模中存在的难点问题,展望了该领域未来的研究发展方向.
摘要: 通过分析服务组合的故障需求,给出服务组合故障处理的框架.该框架采用Petri网来解决服务组合的错误发现及其处理问题.重点讨论了可用服务失败、组件失败及网络故障的情况,并相应地给出了服务组合故障模型.在此基础上对故障处理模型进行分析,给出服务组合故障处理正确性准则,并证明了其正确性.最后,采用CTL (computational tree logic)描述相关性质并提出验证服务组合故障分析的实施算法.仿真结果表明,该方法在处理服务组合故障时具有一定的优越性.
摘要: Internet 流量模型对网络性能管理、QoS、准入控制等都有很重要的意义和作用.首先总结了现阶段已发现的主要网络流量的特性及相关度量参数,概要地介绍网络流量建模的意义和分类,然后按照“传统-自相似-流量建模的新发展”这3 个阶段阐述网络流量建模的发展历程与最新的研究成果,最后针对目前网络流量建模中存在的难点问题,展望了该领域未来的研究发展方向.