删除或更新信息,请邮件至freekaoyan#163.com(#换成@)

软件所在支持编程语言中正则表达式非经典特性的字符串约束求解研究方面取得进展

本站小编 Free考研考试/2022-01-02

近日,中国科学院软件研究所在支持编程语言中正则表达式非经典特性的字符串约束求解研究方面取得进展,提出了带权重的流字符串转换器的新自动机模型,对正则表达式的非经典特性进行形式建模,并根据该模型设计了新的字符串约束求解算法,研制了国际上第一个支持对编程语言中正则表达式非经典特性进行推理的字符串约束求解器OSTRICH,其研究成果被编程语言国际顶级会议POPL 2022录用。
  该项成果研究历时两年,由软件所张立军研究员、吴志林研究员带领的可信智能系统团队软件验证组与德国凯泽斯劳腾工业大学Anthony W. Lin研究组、英国伦敦大学皇家霍洛威学院Matthew Hague研究组和伯贝克学院Taolue Chen研究组、瑞典乌普萨拉大学Philipp Ruemmer研究组合作完成。该项成果是软件验证组成员在POPL上发表的与字符串约束求解相关的第3篇论文。
  正则表达式是计算机科学中的基本概念,但编程语言(比如Javascript)中的正则表达式(简称为Regex)与经典的正则表达式有很大区别:编程语言中的正则表达式一般采用算子的非经典语义(比如贪婪/懒惰的Kleene star),而且包含一些新的特性(比如捕获组和引用)。字符串约束求解器是对操作字符串的程序进行自动分析与验证的基础,但由于对Regex进行形式建模比较有挑战性,已有字符串约束求解器(比如Z3、CVC4)均不支持Regex中的非经典特性。
  可信智能系统团队软件验证组针对该问题进行了两年多的潜心研究,提出了带权重的流字符串转换器的自动机模型(简称为PSST)来对含有Regex的字符串函数的语义进行形式建模,并定义了相应的字符串约束理论。PSST使用权重来对正则表达式算子的贪婪/懒惰语义进行建模,同时使用字符串变量来对捕获组进行建模。而且,我们使用大量的实验验证了PSST语义与Javascript正则表达式实际语义的一致性。
  进一步地,该团队证明了PSST拥有良好的封闭性和算法性质,比如正则保持性,即正则语言在PSST下的原象是正则的。团队利用PSST的良好算法性质设计了字符串约束求解算法,其主要思想是通过计算象和原象来传播正则约束。虽然该团队定义的字符串约束理论一般来讲是不可判定的,但是团队证明了该算法对于直线子集是完备的。团队将该算法在软件验证组开发的OSTRICH字符串约束求解器中进行了实现,并且从开源的正则表达式库中生成了超过19万5千个测试用例来评估算法的性能。实验结果表明算法在精度和效率方面都极大提升了已有的基于符号执行的方法。
  该研究不仅在字符串约束求解研究中具有重要的意义,而且也为Web应用的高精度测试、分析、与验证,以及正则表达式的拒绝服务攻击漏洞的分析与检测奠定了理论基础。
  论文链接

相关话题/软件 设计 智能 系统 论文

  • 领限时大额优惠券,享本站正版考研考试资料!
    大额优惠券
    优惠券领取后72小时内有效,10万种最新考研考试考证类电子打印资料任你选。涵盖全国500余所院校考研专业课、200多种职业资格考试、1100多种经典教材,产品类型包含电子书、题库、全套资料以及视频,无论您是考研复习、考证刷题,还是考前冲刺等,不同类型的产品可满足您学习上的不同需求。 ...
    本站小编 Free壹佰分学习网 2022-09-19
  • 软件所博士生王少东获SMI 2021国际会议最佳论文提名奖
    近日,中国科学院软件研究所计算机科学国家重点实验室图形图像团队在数字几何处理与建模领域取得进展。该研究针对三维模型上叶状结构的快速计算问题,提出使用多重网格法算法(multigrid),大幅提升了叶状结构生成的计算速度,确保了生成计算的收敛性,这将很好地促进叶状结构的实际应用。相关成果以A mult ...
    本站小编 Free考研考试 2022-01-02
  • 软件所参与项目荣获2020年度北京市科学技术进步奖
    在2020年度北京市科技奖励评选中,中国科学院软件研究所参与完成的项目“科技期刊一体化融合出版关键技术研究与产业化应用”荣获北京市科学技术进步奖二等奖。  主要完成单位包括:北京仁和汇智信息技术有限公司、中国科学院文献情报中心、中国科学院软件研究所、中国科学院自动化研究所、中国科学院物理研究所。   ...
    本站小编 Free考研考试 2022-01-02
  • 智能软件研究中心硕士生段旭荣获ISSRE 2021最佳实践论文奖
    近日,中国科学院软件研究所智能软件研究中心武延军、吴敬征课题组在基于深度神经网络的静态代码分析研究中取得进展。该团队提出了基于多类型和多粒度的语义代码表示学习模型——MultiCode,解决了工业场景中涉及多需求的开发任务时面临的开发开销大、模型集成困难、可扩展性受限等问题,实现了在多需求工业场景下 ...
    本站小编 Free考研考试 2022-01-02
  • 软件所金蓓弘、张扶桑课题组荣获ACM UBICOMP 2021杰出论文奖
    普适计算领域的国际顶级学术会议ACM UbiComp (International Joint Conference on Pervasive and Ubiquitous Computing) 2021年度大会于9月21-26日在线上召开。论文“Exploring LoRa for Long-ra ...
    本站小编 Free考研考试 2022-01-02
  • 软件所王青、石琳课题组荣获ASE2021 ACM SIGSOFT杰出论文奖
    近日,中国科学院软件研究所互联网软件技术实验室在开源社区群智挖掘研究中取得进展。该研究面向开源社区中的开发者,针对开发者实时聊天内容中大量有价值的“问题-解决方案”信息,提出了一种多层次模型——面向群智的问题及解决方案自动提取技术(ISPY),有效构建了“问题-解决方案”(Issue-Solutio ...
    本站小编 Free考研考试 2022-01-02
  • 软件所等提出国际首个完全实用的异步共识算法“小飞象” 区块链核心技术取得重大突破
    近日,中国科学院软件研究所张振峰团队与新泽西理工学院唐强团队在区块链核心技术——拜占庭容错(BFT)共识研究中取得突破,提出了首个完全实用的异步共识算法——小飞象拜占庭容错(DumboBFT)算法,该成果《Dumbo: Faster Asynchronous BFT Protocols》发表于网络安 ...
    本站小编 Free考研考试 2022-01-02
  • 软件所四项成果荣获2019年度北京市科学技术奖
    在2019年度北京市科技奖励评选中,中国科学院软件研究所参与完成的四项成果获奖。其中,“高安全低功耗嵌入式系统芯片技术及应用”、“航天嵌入式软件可信保障关键技术和应用”两个项目荣获“2019年度北京市科学技术奖一等奖”,“面向物联网大数据的智能服务平台关键技术及应用”、“基于国产基础软硬件的交通行业 ...
    本站小编 Free考研考试 2022-01-02
  • 软件所发布最大零售场景目标检测计数联合任务数据集——Locount
    在日常购物时,我们不妨畅想一下未来商超的购物场景:无需结算台,消费者取下产品的同时,商品识别算法就可以完成自动结算;无需货架管理员,智能货架管理技术可以实时动态监测商品数量变化,并自动完成数据分析。实现这种智能化消费方式的核心难点在于解决目标检测计数联合任务领域中的遮挡问题。  近日,中国科学院软件 ...
    本站小编 Free考研考试 2022-01-02
  • 软件所高性能计算团队获中科院“先导杯”并行计算应用大奖赛基础算法一等奖
    8月26日,首届中科院“先导杯”并行计算应用大奖赛圆满结束,中国科学院软件研究所并行软件与计算科学实验室高性能计算团队荣获基础算法赛道一等奖。获奖团队由四名研究生组成,分别是:岳星言、张宠、李子薇、曹子健,指导老师为软件所助理研究员孙乔、赵慧,团队历经近五个月的奋战,最终在激烈的角逐中脱颖而出。   ...
    本站小编 Free考研考试 2022-01-02
  • 软件所互联网软件技术实验室博士生刘哲斩获ACM学生研究竞赛研究生组冠军
    近日,中国科学院软件研究所互联网软件技术实验室研究员王青指导的博士生刘哲在ACM学生研究竞赛(The ACM Student Research Competition at ASE 2020)荣获研究生组第一名。  该比赛在第35届IEEE/ACM自动化软件工程国际会议(ASE 2020)期间举行, ...
    本站小编 Free考研考试 2022-01-02