分类

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

技术文章列表

  • C#知识点总结


    C#数据类型的分类:值类型(简单类型(整数型:char、short、int、long,浮点型:float、double,小数型decimal,布尔型bool)、枚举类型enum、结构类型struct)和引用类型
    值类型和引用类型的定义及其类型间区别

    值类型:栈,包括结构体(数值类型,bool型,用户定义的结构体),枚举,可空类型;引用类型:堆,包括数组、类,接口、委托、object、字符串。区别:值类型存取速度快,存储在栈里,直接存放数据;引用类型存取速度慢,存储在堆里,存放数据地址。
    数据类型间的转换方法:隐式、显示
    分支流程控制,if,switch
    循环流程控制,while, do…while, for, foreach,特别是foreach的使用方法。
    理解面向对象最基本的四个特征:抽象、封装、继承、多态
    类的声明、实例化: [访问修饰符] class 类名 [:基类] {类的成员;}定义类之后,可以用定义的类声明对象,然后再通过这个对象来访问其数据或调用其方法。
    理解类及成员的可访问性(访问修饰符的作用)

    public:公共的,访问不受任何限制,允许跨程序集引用,可用来修饰类及其成员。internal:内部的,只允许在当前程序集内部使用,可用来修饰类及其成员。private:私有的,只允许在该类内部使用,不允许其他类访问,只能用来修饰类成员。protected internal:仅限于当前程序集内部使用,只允许该类及其派生类使用, 只能用来修饰类成员。protected:受保护的,只允许该类及其派生类使用, 只能用来修饰类成员。
    掌握类成员(字段、属性、构造函数、常量、方法)及其定义方法,属性get和set访问器

    [访问修饰符] 数据类型 字段名;[访问修饰符] 数据类型 属性名{get{//获取属性的代码,用return 返回值} set{//设置属性的代码,用value赋值}}[访问修饰符] 构造函数名([参数列表]){ [语句;]}[访问修饰符] const 数据类型 常量名=常量的值;[访问修饰符] 返回值类型 方法名 ([参数列表]){语句;……[return 返回值;]}
    方法的重载:同一类中定义多个同名方法,同名方法的参数个数或参数类型不同
    方法的参数传递5种形式及特点

    按值传参:单向值传递,形参值不会影响实参值,string和object(两种引用型)有按值传参效果按引用传参:形、实参变量指向同一个引用,必须对实参明确赋初值(值类型和string类型参数的形参和实参都必须添加ref关键字)输出参数:不需要对实参赋初值(ref除外),但形参必须在赋值后才能用,被调方法结束前必须给输出参数赋值。形参、实参都使用out关键字来声明,一个方法中可允许有多个输出参数引用类型的参数:按引用传递,不用ref或out关键字数组型参数:形参数组前不添加params修饰符,实参是一个数组名;形参数组前添加params修饰符,对应的实参可以是数组名,也可以是数组元素值的列表
    静态类的定义及使用方法,静态成员、静态构造函数等的特点:只包含静态成员的类;静态成员只能用类名引用(和Java、C++不同),静态方法只能访问静态成员;静态构造函数是用来初始化静态字段的,不能有访问修饰符、参数列表和返回值,如:static Student(){}
    抽象类、密封类、接口的定义及使用方法

    只要包含无法实现的成员的类就是抽象类,抽象成员必须在抽象类中声明但抽象类不一定包含抽象成员,抽象类和抽象方法都必须用abstract定义,如:public abstract double Cubage();,抽象属性只声明该属性的数据类型、名字、可访问性等,如:public abstract double Length{get;set;}阻止一个类被其他类继承,sealed只含有公共抽象方法、可以实现多重继承的类,interface
    基本类和派生类的定义方法,派生类中构造函数的定义及调用:基类的构造函数负责初始化基类的成员字段,派生类的构造函数之初始化新添加的成员字段;声明派生类的构造函数时必须使用base关键字向基类的构造函数传递参数
    多态(new,virtual,override)的实现方法及其区别:new是在程序编译时对基类方法的替换,使用virtual定义虚方法再在派生类中使用override是在程序运行时的重写
    虚方法及抽象方法的异同

    异:虚方法有方法体而抽象方法没有;抽象方法只能在抽象类中声明但虚方法不是;要想实例化虚方法可以不重写但抽象方法必须要派生类覆盖即派生类必须重写抽象类的抽象方法但虚方法不必同:修饰符都不能用private、static
    基本类和派生类对象间的类型转换,详见书126页

    派生类对象即使强制转换为基类对象,所引用的仍然是派生类成员Dog x = new Animal();d = (Dog)a;都是错的
    集合的定义及简单使用:高度结构化地存储任意对象的类,可以随意调整大小

    ArrayList al=new ArrayList();Student stu1=(Student)al[0];
    程序错误类型:语法错误、逻辑错误、运行时错误
    程序异常的定义及异常处理方法:系统可能随时发生的不可预期事件:内存不够、磁盘出错、网络连接中断、数据库无法使用:try….catch、try….catch….catch、try…catch…finally
    ADO.NET访问数据库步骤,见书271页

    Connection对象负责连接数据库;Command对象负责对数据库执行命令;DataReader对象负责读取仅向前和只读的数据流;DataSet(数据集)负责建立数据副本和对数据执行命令;DataAdapter对象负责建立数据库和DataSet的联系
    System.Data.SqlClient中用于数据库访问和操作的主要类(Connection, Command, DataReader, DataSet)的使用方法

    Connection:
    String conString=''DataSource=.;DataBase=shujuku;User ID=xx;Pwd=123;/Integrated Security=True;'';SqlConnection conn=new SqlConnection(conString);conn.Open();...;conn.Close();
    Command:
    SqlCommand comm=new SqlCommand(''sql语句'',conn);comm.ExecuteNonQuery();执行增删改语句,返回受影响行数ExecuteReader返回DataReader对象ExecuteScalar执行查询并返回查询结果的第一列第一行
    DataReader://抽象类
    SqlDataReader dr=Command comm.ExecuteReader();while(dr.Read()){(数据类型)dr[索引或列名]//读取某列数据}dr.Close();
    DataSet:
    conn=new SqlConnection(conString);DataSet ds=new DataSet();SqlDataAdapter ad=new SqlDataAdapter("sql语句",conn);da.Fill/Update(ds);dataGridView1.DataSource=ds.Tables[0];

    0 留言 2020-08-11 10:37:35 奖励12点积分
  • 数据库复习要点(数据库知识点总汇)

    一、绪论1.1 概念
    数据:描述事物的符号记录称为数据。数据的种类有数字、文字、图形、图像、声音、正文等。数据与其语义是不可分的
    数据库:数据库是长期储存在计算机内的、有组织的、可共享的数据集合。数据库中的数据按一定的数据模型组织、描述和储存,具有较小的冗余度、较高的数据独立性和易扩展性,并可为各种用户共享
    数据库管理系统:数据库管理系统是位于用户与操作系统之间的一层数据管理软件,用于科学地组织和存储数据、高效地获取和维护数据。DBMS 的主要功能包括数据定义功能、操纵、组织、存储功能、数据库的事务管理、运行管理功能、数据库的建立和维护功能
    数据库系统:数据库系统是指在计算机系统中引入数据库后的系统构成,一般由数据库、数据库管理系统(及其开发工具)、应用系统、数据库管理员构成

    1.2 数据库发展三阶段及特性
    人工管理阶段:数据不保存、应用程序管理数据、数据不共享也不具有独立性
    文件系统阶段:数据可以长期保存、由文件系统管理数据、数据共享性差、冗余度大、独立性差
    数据库系统阶段:数据结构化、共享性好,冗余度低,易扩充、独立性(物理独立性和逻辑独立性)高、由DBMS统一控制管理

    1.3 数据模型现实世界中数据特征的抽象,包括数据结构(二维表/树/网状结构)、数据操作(操作集合)和数据的约束条件(符合实体/参照/自定义完整性)。概念模型、逻辑模型、物理模型。

    实体:客观存在并可以相互区别的事物,可以是具体对象或抽象事件
    属性:实体所具有的的某一特性
    码/键:唯一标识实体的属性集
    域:属性的取值范围
    实体型:某一实体属性的集合
    实体集:性质相同的同类实体的集合
    联系:实体内部的联系及实体之间的联系

    1.4 逻辑模型
    层次模型:有且只有一个结点(根)没有双亲,根以外的其它结点有且只有一个双亲;约束条件:增:如果没有相应的双亲结点值就不能插入子女结点值;删:如果删除双亲结点值,相应的子女结点也被同时删除;改:要修改所有相应记录保证数据一致性
    网状模型:允许一个以上的结点没有双亲;一个结点可以有多于一个的双亲
    关系模型:一张规范化的二维表;支持记录码:唯一标识记录的数据项的集合;保证一个联系中双亲记录和子女记录之间是一对多的联系;可以支持双亲记录和子女记录之间某些约束条件

    物理独立性:当DB的存储结构改变时,由DBA对各个模式/内模式的映象作相应改变,可使模式保持不变,从而应用程序不必修改,保证了数据和程序的物理独立性。
    逻辑独立性:当模式改变时,由数据库管理员对各个外模式/模式的映象作相应改变,可使外模式保持不变。应用程序是根据外模式编写的,从而应用程序不用作出修改,保证了数据和程序的逻辑独立性。
    1.5 思考题
    数据库阶段的数据管理有哪些特点?(2)
    数据独立性和物理独立性在数据库中如何体现?(7)
    DBMS有哪些功能?定义、组织、存储、管理、操纵数据,DB的事务、运行管理,建立和维护
    数据模型的作用及构成要素是什么?(3)
    DBS的用户有哪几类,如何区分?偶然(不常访问需不同信息)、简单(查询更新)、复杂(直接用数据库语言访问数据库)
    DB的三级模式结构描述了什么问题?DB的三级模式结构是指数据库系统是由外模式、模式、内模式三级构成,是数据的三个抽象级别,把数据的具体组织留给DBMS管理。模式也称逻辑模式,是数据库中全体数据的逻辑结构和特征的描述,是所有用户的公共数据视图;外模式也称子模式或用户模式,是数据库用户能看见和使用的局部数据的逻辑结构和特征的描述,是数据库用户的数据视图,是与某一应用相关的数据的逻辑表示;内模式也称存储模式,是数据物理结构和存储方式的描述,是数据在数据库内部的组织方式。
    DBS由哪几部分组成?硬件平台及DB、软件(DBMS,应用系统…)、人员(数据库管理员、用户…)

    二、关系数据库
    域:一组具有相同数据类型的值(基数)的集合,在关系中用域来表示属性的取值范围
    笛卡尔积:对两个关系R和S进行乘操作,产生的关系元组个数为两个关系中元组个数之积
    候选码:关系中的某一属性组的值能唯一标识一个元组而其子集不能,该属性组为候选码
    主码:一个关系有多个候选码(能唯一标识一个元组而其子集不能的属性组),则选定其中的一个为主码
    主属性:主码的诸属性
    非码属性:不包含在任何候选码中的属性
    全码:关系模式的所有属性是这个关系模式的候选码
    外部码:关系R的某一属性组X不是R的码,但是其他某一关系的码

    实体完整性:一个基本关系上的主属性不能取空值。
    参照完整性:一个关系R中的每个元组在他的外码上的取值要么取空值要么等于另一个关系S(关系R的外码对应关系S中的主码)中的某个元组的主码值。

    等值连接
    自然连接:去除重复的列

    思考题
    关系中的元组为什么没有先后顺序 ?关系是一个元组的集合,元组在集合中的顺序不重要
    关系与普通的表格、文件有什么区别 ?关系是一张规范化的二维表格,在关系模式中对关系有规范性限制:关系中的每一个属性值都不可分解,不允许出现相同的元组,没有行序,属性无序但使用时要考虑列的顺序。
    广义笛卡尔积、等值连接、自然连接三者区别?笛卡尔积对两个关系R和S进行乘操作,产生的关系元组个数为两个关系中元组个数之积;等值连接是在笛卡尔积的结果上进行选择操作,从R和S的笛卡尔积中选择对应属性值相等的元组;自然连接是在等值连接上进行投影操作,并去掉重复的公共属性列。当两个关系没有公共属性时,自然连接就转化为笛卡尔积。

    三、关系数据库标准语言SQL、数据库安全性、数据库完整性
    查询 WHERE GROUP BY HAVING LIKE ODER BY 集函数…
    相关子查询… IN EXISTS?

    思考题
    SQL语言有何特点?综合统一、高度非过程化、面向集合的操作方式、以同一种语法结构提供多种使用方式、语言简洁,易学易用
    SQL的定义功能是什么? 模式定义、表定义、视图和索引的定义
    基本表和视图的区别和联系是什么? 视图是从一个或几个基本表(或视图)导出的虚表
    视图有何优点?简洁用户的操作、使用户能以多种角度看待同一数据、对重构数据库提供了一定程度的逻辑性、安全保护机密数据、清晰表达查询
    所有视图是否都可更新?为什么?请举例说明。不是 视图由两个以上基本表导出、字段来自字段表达式或常数、字段来自聚集函数、定义中含GROUP BY、DISTINCT、嵌套查询且内层查询FROM中的表也是导出该表的基本表,一个不允许更新的视图上定义的视图,都不允许更新
    连接查询和嵌套查询的特征分别是什么?一个查询同时涉及两个以上的表;将一个查询块嵌套在另一个查询块的WHERE子句或HAVING短语的条件中的查询

    四、规范化
    函数依赖(简答):对一个属性集上的关系模式的任意一个关系,其中不可能存在两个元组在X函数上的属性值相等但在Y函数上的属性值不等的情况,则称X函数确定Y或Y函数依赖于X,记作X→Y。
    不平凡函数依赖:X→Y,Y⊆X
    平凡函数依赖:X→Y,Y⊆X 如:(学号,课程)→学号
    完全函数依赖F:X→Y,真子集X’Y 如:(学生,课程)→成绩
    部分函数依赖P:X→Y且Y不完全依赖于X
    传递函数依赖:Y对X不平凡函数依赖,YX,Y→Z 如:(学生、宿舍、面积)

    给出模式及其语义,写出函数依赖(部分/完全/传递)码:一个关系模式的属性或属性集完全函数依赖于K,则K为此关系模式的候选码,若有多个则选一个做主码;不可能出现两个元组在码上的值相同在其他值不同
    给出关系模式和函数依赖,判断第几范式
    R∈1NF:一个关系模式R的所有属性都是不可分的基本数据项
    (无非主对码的部分…)R∈2NF:关系模式R∈1NF,并且每一个非主属性都完全函数依赖于R的码 每一个非主属性完全函数依赖于任一个候选码
    (无非主对码的传递…)R∈3NF:关系模式R<U,F> 中若不存在这样的码X、属性组Y及非主属性Z(Z  Y), 使得X→Y,(Y→X)Y→Z成立,则称R<U,F>∈3NF
    (无主对码的部分和传递…)R∈BCNF:设关系模式R<U,F>∈1NF,若X→Y且YX时X必含有码,则R<U,F>∈BCNF 每一个决定因素都包含码
    多值依赖X→→Y:一对(x,z)值,有一组Y的值,这组值仅仅决定于x值而与z值无关
    (限制关系模式间无非平凡且非函数依赖的多值依赖)R∈4NF:关系模式R<U,F>∈1NF,如果对于R的每个非平凡多值依赖X→→Y(Y  X),X都含有码,则称R<U,F>∈4NF

    五、数据库设计
    (大题)给出数据库要求,画出E-R图,转换为模式(需求分析、概念结构设计、逻辑结构设计)
    数据字典:数据项(不可再分的数据单位)、数据结构(反应数据之间组合关系)、数据流(数据结构在系统内传输的路径)、数据存储(数据结构停留和保存的地方,数据流的来源和去向之一)、处理过程(描述处理过程的说明性信息)的含义,写出某个应用系统的数据字典

    思考题
    数据库的生命周期分为哪几个阶段?6 需求分析 概念结构设计、逻辑结构设计、物理结构设计、数据库实施、数据库运行和维护
    数据库结构设计在生命周期中的地位如何?
    数据库概念设计的重要性和设计步骤。将需求分析阶段的数据分类组织,确定实体、实体的属性、实体之间的联系模型,画E-R图。
    数据库逻辑设计的重要性和设计步骤。把概念结构设计阶段的E-R图转换为与DBMS支持的数据模型相符的逻辑结构
    数据库物理设计的重要性和设计步骤为一个给定的逻辑数据模型选取一个最适合应用要求的物理结构。1确定数据库物理结构2对物理结构进行评价
    最后一道大题 习题(学校/零件)某学校有若干系,每个系有若干学生,若干课程,每个学生只在一个系学习,同一门课只在一个系开设,某个学生选修了若干课程,每门课有若干学生选修。其中,学校包括属性:学校代码、学校名称、学校地址;系包括属性:系名、系代号、系主任名和电话;学生包括属性:学号、姓名、年龄、性别、所在系代号;课程包含属性:课程号、课程名;学生上课后有一个成绩。今要建立该学生选修课程的数据库,请你设计:关于此学校数据库的E-R图,并把该E-R图转换为关系模型,并标识出每个关系模式的主码。

    六、数据库恢复技术事务:用户定义的一个数据库操作序列,要么全做要么不做,是一个不可分割的工作单位ACID原子性(事务是数据库的逻辑工作单位)、一致性(事务执行的结果必须是数据库从一个一致性状态变到另一个一致性状态)、隔离性(一个事务的执行不能被其他事务干扰)、持续性(一个事务一旦提交他对数据库中数据的改变就应该是永久性的)
    三种故障和恢复
    事物内部的故障(事务在运行过程中未运行至正常终止点就夭折了):撤销事务UNDO、强行回滚该事务ROLLBACK、清除该事务对数据库的所有修改
    系统故障(正常运行被破坏、正在运行的事务非正常终止、内存数据库缓冲区的信息全丢失、外部存储设备上的数据没受影响):重启时恢复程序要强行撤销所有未完成事务UNDO、重做所有已提交的事务REDO
    介质故障(硬件故障使存储在外存中的数据丢失):数据转储

    静态转储:在系统无运行事务时进行转储,转储开始时一致性,转储期间不允许对数据库的任何存取、修改活动 简单但降低可用性
    动态转储:与事务并发进行,转储期间允许对数据库存取或修改不能保证副本中的数据正确有效和登录日志文件(后两种故障时用到)
    思考题
    什么是事务?事务有哪些重要属性 ?(1)
    什么是数据库的恢复 ?
    什么是数据库中数据的一致性?
    为什么事务的非正常结束会影响数据库数据的一致性?试举例说明。事务执行的结果必须是使数据库从一个一致性状态变到另一个一致性状态。如果数据库系统运行中发生故障,有些事务尚未完成就被迫中断,这些未完成事务对数据库所做的修改有一部分已写入物理数据库,这时数据库就处于一种不正确的状态,或者说是不一致性状态。例如,某工厂的库存管理系统中,要把数量为Q的某种零件从仓库1移到仓库2存放,则可以定义一个事务T。T包括两个操作:Q1=Q1-Q,Q2=Q2+Q。如果T非正常终止时只做了第一个操作,则数据库就处于不一致性状态,库存量无缘无故少了Q。
    数据库恢复的基本原理是什么?冗余
    数据库恢复的基本技术有哪些?数据转储和登录日志文件

    七、并发控制
    丢失修改:事务1、2读入同一数据并修改,2的提交结果破坏了1提交的结果,导致1的修改被丢失
    不可重复读:指1读取数据后,2执行更新操作,使1无法再现前一次读取结果
    脏数据:1修改某一数据,并将其写回磁盘;2读取同一数据后;1由于某种原因被撤消,这时事务1已修改过的数据恢复原值;事务2读到的数据就与数据库中的数据不一致,是不正确的数据

    思考题
    什么是事务的并发操作,有哪几种类型 ?事务的并行执行 2交叉并发和同时并发
    并发操作会带来哪几种问题,这些问题的特征和根由是什么?破坏I、C +(1)
    什么是封锁?基本的封锁类型有几种?事务T在对某个数据对象(例如表、记录等)操作之前,先向系统发出请求,对其加锁。加锁后事务T就对该数据对象有了一定的控制,在事务T释放它的锁之前,其它的事务不能更新此数据对象。 2 排它锁X、共享锁S
    数据库恢复的基本原理是什么?冗余。数据库中任何一部分被破坏或不正确的数据可以根据存储在系统别处的冗余数据来重建。
    数据库恢复的基本技术有哪些?数据转储和登录日志文件是数据库恢复的基本技术。当系统运行过程中发生故障,利用转储的数据库后备副本和日志文件就可以将数据库恢复到故障前的某个一致性状态。
    为什么要引进意向锁?意向锁的含义是什么?为提高封锁子系统的效率。该封锁子系统支持多种封锁粒度。原因是:在多粒度封锁方法中一个数据对象可能以两种方式加锁——显式封锁和隐式封锁。因此系统在对某一数据对象加锁时不仅要检查该数据对象上有无(显式和隐式)封锁与之冲突,还要检查其所有上级结点和所有下级结点,看申请的封锁是否与这些结点上的(显式和隐式)封锁冲突,显然,这样的检查方法效率很低。为此引进了意向锁。含义:对任一结点加锁时,必须先对它的上层结点加意向锁。例如事务T要对某个元组加X锁,则首先要对关系和数据库加ix锁。对关系和数据库加ix 锁,表示它的后裔结点——某个元组拟(意向)加X锁。引进意向锁后,系统对某一数据对象加锁时不必逐个检查与下一级结点的封锁冲突了。例如,事务T要对关系R加X锁时,系统只要检查根结点数据库和R本身是否己加了不相容的锁(如发现已经加了ix,则与x冲突),而不再需要搜索和检查R中的每一个元组是否加了X锁或S锁。
    0 留言 2020-08-11 10:37:21 奖励16点积分
  • 共识算法:实用拜占庭容错算法(PBFT)


    本文原作为:fatcat22,如需转载请注明来源。原文地址:https://yangzhe.me/2019/11/25/pbft/

    最近在学习区块链方面的知识,看到这篇博文讲得很好,故转载分享!
    引言在之前的文章中,我们介绍了什么是「拜占庭将军问题」,也了解了原论文中的解决方案。但那些方案只是理论上的解决办法,若真的在现实中使用就会有各种各样的问题。因此在那之后,又提出了一些可在真实生产环境中使用的解决拜占庭将军问题的方法,本文将要介绍的「实用拜占庭容错算法」(Practical Byzantine Fault Tolerance, 简称 PBFT)就是其中一种。
    从名称上就可以看出,PBFT 就是冲着可在实际应用中使用而发明的。这篇文章里,我们将详细了解一下 PBFT 算法的相关细节。文章中的多数讨论来自于原始论文,不过这篇文章写得也很不错,给了我一些启发。
    系统模型在介绍 PBFT 的算法步骤之前,我们先了解一下使用 PBFT 算法的分布式系统的概念,和算法对系统的一些要求。

    首先,PBFT 对系统内的结点数量是有要求的。与拜占庭将军问题类似,PBFT 要求系统内的结点数量 nnn 不小于 3f+13f+13f+1,其中 fff 为「恶意结点」的数量。这里的「恶意结点」可以是故意作恶的结点,也可以是被攻击被控制的结点,甚至是失去响应的结点,总之只要是不正常的,都可以认为是恶意的。
    其次,PBFT 将系统内的每个结点分成了两类:主结点和从结点。任一时刻内,只有一个主结点,其它结点都是从结点。但主结点是可以被更换的(更换主结点被称为「域转换」(View Change))。无论是主结点还是从结点,他们都使用状态机机制记录自己的操作。如果各结点的操作是一致的,那么它们的状态机的状态会一直保持一致。
    再次,向 PBFT 系统发送请求的端叫做「客户端」。当某个客户端想要向系统发送请求时,一般情况下,它会将请求发给当前的主结点;非一般情况下,它会将请求广播给所有结点。无论哪种情况,客户端都直接从各个结点(包括主结点)接收请求返回的数据。
    第四,在论文中,作者假设客户端等待上一个请求完成以后,才会发送下一个请求。也就是说主结点和从结点们在某一时刻只会处理一个请求。这是一种同步发送请求的方式。如果客户端不等上一个请求返回就再次发送请求(即异步发送请求),那么请求的响应顺序可能不会是客户端发送的顺序。
    第五,PBFT 中有一个「域」( view )的概念(一般翻译成「视图」,但我觉得「视图」这个词并不能表达原术语的意思,所以我大胆将它翻译成「域」)。某个结点担任主结点的过程,就是一个域。如果担任主结点的结点发生了变化,就是发生了「域转换」(View Change)。域是有编号的,每发生一次域转换,域编号就递增一次。如果将每个结点从 0 开始编号,那么我们可以通过算式 i=v mod ∣R∣i=v \space mod \space |R|i=v mod ∣R∣得到当前主结点的编号 iii:其中 vvv 为当前的域编号, ∣R∣|R|∣R∣ 为结点数量。(如果把「域」比作「朝代」,可能会比较好理解一些:一个结点开始担任主结点,表示一个朝代的开始;主结点发生变更时,表示一个朝代的变更,朝代号就是加 1)
    最后,PBFT 中各结点通信信息是经过签名的。也就是说,任何一个结点都无法修改别的结点发送的消息,只能原封不动的拷贝、转发或存储。所以可以想象一下, PBFT 算法与介绍拜占庭将军问题的文章中的 SMSMSM 算法应该是有相同的地方的。

    以上就是 PBFT 系统模型的要点。看完这些你可能似懂非懂,心中有很多疑问题。比如为什么需要 3f+13f+13f+1 个结点?域到底起什么作用?这些问题我们会在后面作解答。这里只需了解这些概念和限制,相信在后面理解算法的过程中,很多问题自然就会消散了。

    在这里谈下我自己的理解:为什么n>3f?(n是节点总数,f是恶意节点)
    我们要在收到n-f条消息的时候,就必须做出决定,因为若有f个节点可以不发消息,这时节点最多能接收到n-f条消息。所以,我们必须要在接收到n-f条消息时做出决定。
    当在通信网络中,节点接收到n-f条消息时,最坏的情况是未接收到的消息都是诚实节点发的,而接收到的消息中有f条消息正好是恶意节点发的,那么这时要想做出少数服从多数的正确决定,诚实节点消息必须多于恶意节点消息:(n-f)-f>f。

    如果我来发明这个算法…我发现很多「高大上」的东西,其底层的逻辑通常都很朴素,并没有复杂到像我这样的普通人永远也想不出来的程度。所以我很喜欢在理解了某问题的解决方法以后,再假设我不知道这个方法但仍然遇到了问题,然后把解决方法「自己想出来」。所以这里我决定在文章里来这么一次。
    前面我们已经给了应用 PBFT 的系统的一些概念和限制了,总结一下就是:正常情况下,客户端发送请求给主节点,然后等待各个从节点返回数据。而我们要做的是,保证多数节点(无论是主结点还是从结点)返回一致的数据给客户端。
    OK,现在就让我们来想象一下这个过程。现在客户端发送数据给主结点了,主结点该怎么办呢?它不但要自己响应这一请求,还要把这一请求发送给所有从结点,让所有从结点进行响应。所以这里主结点做了两件事:

    一是自己响应客户端的请求
    二是将客户端的请求转发给所有从节点

    现在每个从结点都收到了主结点转发的请求,那么从结点们应该开始响应这个请求吗?注意这是一个无法信任某个人的世界,所以从结点们不知道主结点是不是可信,它们不会直接执行收到的请求的。那从结点们该怎么办呢?
    答案就是「少数服从多数」:如果从结点可以确定其它大多数从结点收到的请求与自己收到的请求是一样的,那么就可以响应这个请求。所以从结点们一边将自己收到的请求广播给其它从结点,一边收取并记录其它从结点广播过来的请求。当某个从结点收集到了足够多的从结点广播的请求,并且这些请求与自己从主结点那里收到的一致,它就认为主结点是可信的、这个请求是可以响应的。(这一过程与拜占庭将军问题的论文中的 SMSMSM 算法很像,具体可参考之前的文章)。
    现在收集到足够多的从结点可以确定主结点是可信的,那么它是否可以立即执行这个请求呢(在 SMSMSM 算法中确实是立即执行的)?答案是不可以。虽然某个从结点确认了请求是可以响应的,但它并不能确定别的从结点也确认了。所以如果此时立即执行请求,我们并不能保证结点间的状态一致。举个例子,比如可能有某个从结点由于暂时的网络问题,只能向外广播消息,却收不到其它结点的消息。因此这个结点就收不到足够多的其它从结点广播的请求,因而也不会认为这个请求是可以响应的。最终的结果是有的结点响应了这个请求,有的没有响应,无法保证结点间的状态是一致的。
    那怎么办呢?既然无法确定别的结点是否确认了这个消息是可响应的,那就确定一下呗。所以从结点需要多做一步,从结点此时并不马上响应请求,而是给所有其它结点广播一条消息:「我认可了某某请求」。然后它开始等待其它从结点的同样的消息。如果某从结点发现大多数结点都发出了这样一条消息,它就确定大多数结点认可这一请求是可以响应的(而不像刚才那样只知道自己认可是可响应的,别人是否认可它不知道)。所以现在它可以愉快的执行并响应这一请求。如果所有正常的结点都这样做,那么所有正常的结点都知道自己可以响应这一请求,也知道其他多数结点也同意响应这个请求,那么最后大多结点的状态在响应完这个请求后,仍然是一致的。
    稍微总结一下这一过程,你会发现各结点先是做了两步:

    第一步是广播「认可当前请求」的消息、并从其它结点那接收同样的消息
    第二步是广播「我认可了某某请求」的消息、并从其它结点那接收同样的消息。然后当接收到多数结点发送的「我认可了某某请求」消息时,才真正执行和响应请求

    这就是我能想像出来的保证多数结点状态一致的过程,也是白话版的 PBFT 算法的主要过程。当然刚才描述的这个过程仍有不少问题需要解决(比如当前主结点是恶意的怎么办?再比如即使收到了大多数结点发送的「我认可了某某请求」,但因为一些原因仍未执行请求怎么办?),但主要的流程就是刚才描述的那样,其它问题只不过是对一些异常状态的处理而已。
    其实各结点「两步走」的想法,和建立 TCP 连接的「三次握手」是非常相似的:虽然我能确定对方是正常的,但我确定不了对方对我的看法(对方是否认为我是正常的),所以只得再增加一步,以完成这一确定。
    说完了我自己的朴素的 PBFT 的逻辑,下面我们就来看看真正的 PBFT 是什么样子的。
    PBFT 算法下面我们就来看看真正的 PBFT 算法是什么样子的。我们首先了解一下在正常情况下,PBFT 是如何执行的;然后介绍一下 检查点(checkpoint)的概念;最后学习一下异常发生时的域转换(View Changes)的逻辑,和主结点不响应这种异常情况的处理方法。(其实检查点不算是 PBFT 的一个重点的概念,并且也很好理解。但要想理解域转换,就需要先理解检查点的概)
    正常情况下的流程这一小节里我们来了解一下在正常情况下 PBFT 算法的流程。但在这之前,我们需要先介绍一下后面用到的一些符号的意义。

    首先,我们在文章的开头提到过,PBFT 系统中各结点的消息是经过签名的,所以在下面的描述中,我们使用 <m>σi<m>_{\sigma i}<m>​σi​​ 代表由结点 iii 签名的消息 mmm;使用 D(m)D(m)D(m) 或 ddd 代表消息 mmm 哈希。
    其次,前面也说过,在 PBFT 中每一个域都有一个编号,后面我们记为 vvv。当发生域转换时,vvv 会递增加 1。每个结点也有一个编号,一般记为 iii,结点的编号从 0 开始,直至结点总数 ∣R∣−1|R|-1∣R∣−1。所以我们可以使用 i=v mod ∣R∣i=v \space mod \space |R|i=v mod ∣R∣ 来计算当前哪个结点是主结点。

    PBFT 的核心是三个阶段:pre-prepare、prepare、commit。所以这里我们先单独介绍一下这三个阶段,然后再看一下整体的正常流程。
    PBFT 三阶段PBFT 的三个阶段按执行顺序是 pre-prepare 阶段、 prepare 阶段、 commit 阶段。pre-prepare 阶段起始于主结点收到客户端的请求以后。下面我们详细了解一下每个阶段的细节。小节的最后我们会放上原始论文中的示意图,在经过说明之后,这个示意图会更加容易明白。
    pre-prepare主结点收到客户端发送的请求之后,开始 pre-prepare 阶段。首先主结点ppp 为收到的请求分配一个序号,记为 nnn(nnn 必须未被分配给其它请求,且比最近一次的请求的序号大)。然后广播消息 <<PRE−PREPARE,v,n,d>σp,m> <<PRE-PREPARE,v,n,d>_{\sigma p},m><<PRE−PREPARE,v,n,d>​σp​​,m> 给所有从结点。其 mmm 为结点收到的客户端请求; vvv 代表当前的域编号(view number);nnn 为刚才分配给 mmm 的序号;ddd 为 mmm 的哈希值。
    注意这里的参与签名的 <PRE−PREPARE><PRE-PREPARE><PRE−PREPARE> 消息中,并不包含 mmm 本身。这是因为一方面 <PRE−PREPARE><PRE-PREPARE><PRE−PREPARE> 消息可能在域转换时还会被用到,而那时并不需要重新发送 mmm 本身;另一方面,将 mmm 与 <PRE−PREPARE><PRE-PREPARE><PRE−PREPARE> 消息分开,可以更方便针对某些情况做优化,比如在 mmm 较大时使用更好的方式发送 mmm 本身。
    当从结点收到 <PRE−PREPARE><PRE-PREPARE><PRE−PREPARE> 消息后,会对其进行验证,满足以下条件才会通过验证:

    mmm 的签名和 <PRE−PREPARE><PRE-PREPARE><PRE−PREPARE> 消息的签名都是正确的,且 <PRE−PREPARE><PRE-PREPARE><PRE−PREPARE> 消息中的 ddd 确是 mmm 的哈希
    从结点当前的域编号与 <PRE−PREPARE><PRE-PREPARE><PRE−PREPARE> 消息中的一致,都为 vvv
    从结点之前没收到过相同的 <PRE−PREPARE><PRE-PREPARE><PRE−PREPARE> 消息
    在 <PRE−PREPARE><PRE-PREPARE><PRE−PREPARE> 消息中的 nnn 在区间 [h, H] 内

    最后一条可以避免恶意的主结点滥用序号值,比如将序号值设置得非常大。我们在介绍 checkpoint 时会说明如何设置 hhh 和 HHH 的值。
    prepare如果某个从结点验证通过了某条 <PRE−PREPARE><PRE-PREPARE><PRE−PREPARE> 消息,那么它将进入 prepare 阶段,并广播消息 <PREPARE,v,n,d,i>σi <PREPARE,v,n,d, i>_{\sigma i}<PREPARE,v,n,d,i>​σi​​ 。(如果 <PRE−PREPARE><PRE-PREPARE><PRE−PREPARE> 消息验证不通过,就忽略它,什么也不做)
    在从结点发出 <PREPARE><PREPARE><PREPARE> 消息的同时,它也会接收别人广播过来的 <PREPARE><PREPARE><PREPARE> 消息,并对其进行验证。满足以下条件才会通过验证:

    <PREPARE><PREPARE><PREPARE> 消息的签名是正确的
    从结点当前的域编号与 <PREPARE><PREPARE><PREPARE> 消息中的一致,都为 vvv
    在 <PREPARE><PREPARE><PREPARE> 消息中的 nnn 在区间 [h, H] 内

    这里我们需要定义一个函数 prepared(m,v,n,d,i)prepared(m,v,n,d,i)prepared(m,v,n,d,i):如果某结点 iii 验证通过了以下数据:

    mmm 本身
    关于 mmm 的 <PRE−PREPARE,v,n,d> <PRE-PREPARE,v,n,d> <PRE−PREPARE,v,n,d> 消息
    2f 条其它结点(不包含自己)发送过来的、与 <PRE−PREPARE><PRE-PREPARE><PRE−PREPARE> 消息相匹配的 <PREPARE><PREPARE><PREPARE> 消息(匹配的定义是,它们的vvv、nnn 以及 mmm 的哈希 ddd 是完全一样的)

    我们就定义 prepared(m,v,n,d,i)prepared(m,v,n,d,i)prepared(m,v,n,d,i) 的值为 truetruetrue,否则为falsefalsefalse。
    commit如果对于某个结点 iii ,prepared(m,v,n,d,i)prepared(m,v,n,d,i)prepared(m,v,n,d,i) 为 truetruetrue,那么这个结点将进入commit 阶段,并广播消息 <COMMIT,v,n,i>σi <COMMIT,v,n,i>_{\sigma i}<COMMIT,v,n,i>​σi​​ 。
    类似于 prepare 阶段,从结点发送 <COMMIT><COMMIT><COMMIT> 消息的同时,也会接收别的结点广播过来的 <COMMIT><COMMIT><COMMIT> 消息,并对其进行验证。满足以下条件才会通过验证:

    <COMMIT><COMMIT><COMMIT> 消息的签名是正确的
    从结点当前的域编号与 <COMMIT><COMMIT><COMMIT> 消息中的一致,都为 vvv
    在 <COMMIT><COMMIT><COMMIT> 消息中的 nnn 在区间 [h, H] 内

    类似于 prepare 阶段,我们这里也要定义一个函数 committed−local(m,v,n,d,i) committed-local(m,v,n,d,i) committed−local(m,v,n,d,i):如果某结点 iii 满足以下条件:

    要求 prepared(m,v,n,d,i) prepared(m,v,n,d,i) prepared(m,v,n,d,i) 的值为 truetruetrue
    验证通过了 2f 条其它结点(不包括自己)发送过来的、与 <PREPARE><PREPARE><PREPARE> 消息相匹配的 <COMMIT><COMMIT><COMMIT> 消息(匹配的定义是,它们的vvv、nnn 以及 mmm 的哈希 ddd 是完全一样的)

    我们就定义 committed−local(m,v,n,d,i) committed-local(m,v,n,d,i) committed−local(m,v,n,d,i) 为 truetruetrue,否则为 falsefalsefalse。
    如果某结点 iii 的 committed−local(m,v,n,d,i) committed-local(m,v,n,d,i) committed−local(m,v,n,d,i) 为 truetruetrue,那么它就可以响应请求 mmm、将结果更新到自己的状态机中、并返回结果给客户端了。
    下面就是原始论文中使用的三阶段的示意图,其中 0 是主结点,3号是恶意结点不对请求进行响应(我一开始看这个图是有些懵的,但明白了整个过程以后再看,就很清楚了):

    正常情况下的完整流程介绍完了最核心的三阶段,我们将其放在整个 PBFT 的流程中,看一下在不出意外的正常情况下,PBFT 的完整流程:

    客户端向主结点发起请求,记为 <REQUEST,o,t,c>σc <REQUEST,o,t,c>_{\sigma c} <REQUEST,o,t,c>​σc​​ 。其中 ooo 代表客户端请求的操作( operation );ttt 代表时间戳;ccc 为客户端自己的标识。这里通过 ttt 来保证同一请求只会被发送和处理一次:如果主结点收到两个完全一样的请求,它将丢弃重复的请求;如果同一操作需要先后执行两次,客户端应该先后构造两个请求,且这两个请求的时间戳是不一样的。
    主结点收到请求后,立即启动三阶段的共识过程,让所有从结点参与请求的处理。三阶段的共识过程就是我们前面介绍的 pre-prepare、prepare、commit。
    三阶段执行完成后,如果对于某一结点 iii, committed−local(m,v,n,d,i)committed-local(m,v,n,d,i)committed−local(m,v,n,d,i) 的值为 truetruetrue,则结点开始执行请求 mmm。执行成功后更改自己本地状态机的状态,并将结点直接返回给客户端。
    针对同一请求,如果客户端收到了 f+1 个相同的返回结果,那么它就把这个结点作为最终的结果。

    这就是 PBFT 在正常情况下的完整流程。
    在第 3 步中,你可能会有疑问,虽然对于结点 iii, committed−local(m,v,n,d,i)committed-local(m,v,n,d,i)committed−local(m,v,n,d,i) 为 truetruetrue,即结点 iii 确实可以响应 mmm 了,但结点 iii 如何确定其它结点的 committed−locallocalcommitted-locallocalcommitted−locallocal 为 truetruetrue 了呢?如果大多数其它结点的 committed−locallocalcommitted-locallocalcommitted−locallocal 不为 truetruetrue,它们就不会响应 mmm,那么结点 iii 的状态岂不是与其它结点的状态不一致了吗?
    确实,在第 3 步中,某个正常结点的 committed−locallocalcommitted-locallocalcommitted−locallocal 为 truetruetrue,并不真正代表其它所有正常结点的 committed−locallocalcommitted-locallocalcommitted−locallocal 都为 truetruetrue,但这其实是一种特殊情况,而不是正常情况。正常情况下,某结点发送了 <COMMIT><COMMIT><COMMIT> 消息且验证通过了 2f 条其它结点发送的 <COMMIT><COMMIT><COMMIT> 消息(因而它的 committed−locallocalcommitted-locallocalcommitted−locallocal 为 truetruetrue),其它正常结点应该也可以接收到 2f 条 <COMMIT><COMMIT><COMMIT> 消息、因而也可以达到 committed−locallocalcommitted-locallocalcommitted−locallocal 为 truetruetrue 的状态。
    这一小节里我们并没有讨论「特殊情况」下的解决方法(所以小节的名字才叫「正常情况下的完整流程」)。那么要解决刚才的疑问中的特殊情况(包括其它特殊情况,比如主结点是恶意的),需要靠后面的小节介绍的域转换才行。
    检查点( checkpoints )在介绍域转换之前,我们首先要介绍一下 checkpoint 的概念。一般情况下,每个结点需要保存所有的历史数据和状态机的每个历史状态,以便在需要的时候可以复查。但随着系统运行的时间越来越长,数据就会越来越多,最终肯定有存不下的情况。所以我们需要一种机制,可以放心的丢弃以前的历史数据,又不致于影响系统的运行和结点间的信任。
    原始论文中给出的解决方法就是检查点(checkpoints)机制。所谓「检查点」,其实就是某一时刻结点状态机的状态。系统中的每个结点都会按相同的时期间隔(比如每隔 100 个请求序号)将状态机的状态创建为检查点。
    如果某结点自顾自的创建的一个检查点,那么这个检查点是没有可信度的,只有它自己才相信这个检查点的正确性。因此如果一个结点想要创建一个别人都信服的检查点,除了创建检查点本身,还要创建这个检查点的「证明」,这个证明说明了大多数结点都认可了这个检查点。一个有证明的检查点,被称为「稳定检查点」(stable checkpoint)。只有稳定检查点之前的历史数据,才是可以放心删除的。
    那么如何创建稳定检查点呢?假设一个结点 iii 最新处理的请求序号为 nnn,此时状态机的状态的哈希值为 ddd。它想在此时创建一个稳定的检查点,那么它将创建并广播消息 <CHECKPOINT,n,d,i>σi <CHECKPOINT,n,d,i>_{\sigma i} <CHECKPOINT,n,d,i>​σi​​ 。同时它将收集其它结点广播的 CHECKPOINTCHECKPOINTCHECKPOINT 消息,如果它收到 2f 条不同结点广播出来的、序号为 nnn、状态哈希为 ddd 的 CHECKPOINTCHECKPOINTCHECKPOINT 消息,那么它就创建了一个稳定检查点,这 2f+1 条消息(包含自己的消息)就是这个稳定检查点的证明。
    前面我们也提到了一个区间 [h, H] ,这个区间主要是为了防止恶意主结点滥用序号值。但我们没提过如何设置 h 和 H 的值。有了稳定检查点,这两个值就好设置了。论文中提出可以将 h 设置为当前最新的稳定检查点的序号值,而 H 设置一个相对较大的值,保证正常情况下在创建下一个稳定检查点时,其序号值也不会超过 H。比如,如果系统正常情况下每隔 100 个请求序号就创建一个检查点,那么 H 可以设置为 200。
    了解了检查点的概念,下面我们再来看看域转换时会发生什么。
    域转换(View Changes)前面我们提到过,所谓「域」,就是某个结点作为主结点的整个过程(就像中国古代「朝代」的概念)。每个域都有一个编号。每当主结点发生一次变换,域编号就递增加 1,这个过程也就是所谓的「域转换」。可以看到,其实域转换主要是主结点的变换。
    为什么要设计「域」这个概念呢?这主要是为了保持整个系统的「活性」(liveness)。前面我们说过, PBFT 的系统模型就是主结点、从结点的模式,这种模式严重依赖主结点的正确性:如果主结点是正常的,那么它会给客户端请求分配正确的序号,然后将正确的 <PRE−PREPARE><PRE-PREPARE><PRE−PREPARE> 消息广播给所有从结点,各结点才能最终达成一致共识;如果主结点是恶意的,它就可能给各从结点发送各不相同的 <PRE−PREPARE><PRE-PREPARE><PRE−PREPARE> 消息,那么从结点肯定无法达成共识。可见如果没有机制可以将这样的恶意主结点换掉,那么不管有多少个正常的从结点,这个系统依然是废的,永远无法处理任何请求。所以在设计 PBFT 更换主结点的能力时,作者定义了「域」的概念,并将更换主结点的过程定义为「域转换」。
    那么什么时候会发生域转换呢?其实任何会发生异常的地方,都有可能导致发生域转换,总结下来,主要有以下情况可能会发生异常:

    从结点发送 <PREPARE><PREPARE><PREPARE> 消息后,在一定时间内没有收到 2f 条其它结点广播的同样的 <PREPARE><PREPARE><PREPARE> 消息
    从结点发送 <COMMIT><COMMIT><COMMIT> 消息以后,在一定时间内没有收到 2f 条其它结点广播的同样的 <COMMIT><COMMIT><COMMIT> 消息
    主结点不响应客户端的请求

    上面三种情况总结起来,其实都是「超时」(第三种情况其实是主结点不响应的情况,我们会在下一小节详细讨论)。可以说任何该发生却没有发生的情况,都会引起域转换。
    下面我们来看看如何进行域转换。对于任一结点 iii,假设它当前的域编号是 vvv。如果发生了前面提到的超时情况,则结点 iii 就会发起域转换,具体步骤如下:

    结点 iii 暂时停止接收和处理消息(除了 <CHECKPOINT><CHECKPOINT><CHECKPOINT>、<VIEW−CHANGE><VIEW-CHANGE><VIEW−CHANGE>、<NEW−VIEW><NEW-VIEW><NEW−VIEW> 三种消息),并广播消息 <VIEW−CHANGE,v+1,n,C,P,i>σi <VIEW-CHANGE,v+1,n,C,P,i>_{\sigma i}<VIEW−CHANGE,v+1,n,C,P,i>​σi​​ 。其中 nnn 是结点 iii 最新的稳定检查点的请求序号;CCC 是 nnn 对应的稳定检查点的证明(2f+1 条 <CHECKPOINT><CHECKPOINT><CHECKPOINT> 消息);PPP 是一个集合,集合中的每一项为某结点 iii 中序号大于 nnn 且处于 preparedpreparedprepared 状态的请求的信息 PmP_mP​m​​。这里 PmP_mP​m​​ 其实就是 mmm 对应的 <PRE−PREPARE><PRE-PREPARE><PRE−PREPARE> 消息和 2f 条相匹配的 <PREPARE><PREPARE><PREPARE> 消息。
    当域编号为 v+1v+1v+1 的主结点 ppp(此时它其实还不是主结点)收到 2f 条步骤 1 中发送的 <VIEW−CHANGE><VIEW-CHANGE><VIEW−CHANGE> 消息,则它广播一条消息 <NEW−VIEW,v+1,V,O>σp <NEW-VIEW,v+1,V,O>_{\sigma p}<NEW−VIEW,v+1,V,O>​σp​​ 给所有其它结点。
    其中 VVV 是新主结点 ppp 收到的 2f+1 条(包括自己的) <VIEW−CHANGE><VIEW-CHANGE><VIEW−CHANGE> 消息的集合;OOO 是一些 <PRE−PREPARE><PRE-PREPARE><PRE−PREPARE> 消息的集合。集合 OOO 是这样计算出来的:

    1.主结点 ppp 计算出一个请求的序号范围。其中最小值我们记为 min−smin-smin−s,它的值为 VVV 中所有稳定检查点的请求序号的最大值;最小值我们记为 max−smax-smax−s,它的值为 VVV 中所有处于 preparedpreparedprepared 状态的请求的序号的最大值。
    2.主结点 ppp 使用新的域编号 v+1v+1v+1 为每一个序号位于 [min−s,max−s][min-s,max-s][min−s,max−s] 范围内的请求创建一个 PRE−PREPAREPRE-PREPAREPRE−PREPARE 消息,并将其加入到集合 OOO 中。创建 <PRE−PREPARE><PRE-PREPARE><PRE−PREPARE> 消息时,假设当前的序号为 nnn,有两种情况:

    (1).序号 nnn 对应的请求信息存在于集合 PPP 中。此时主结点 ppp 创建如下消息:<PRE−PREPARE,v+1,n,d>σp <PRE-PREPARE,v+1,n,d>_{\sigma p}<PRE−PREPARE,v+1,n,d>​σp​​。其中 ddd 是集合 VVV 中序号为 nnn 且域编号最大的 <PRE−PREPARE><PRE-PREPARE><PRE−PREPARE> 消息对应的请求的哈希。
    (2).序号 nnn 对应的请求信息不在 PPP 中,这表明此消息已被成功处理。此时主结点 ppp 创建如下消息:<PRE−PREPARE,v+1,n,dnull>σp <PRE-PREPARE,v+1,n,d_{null}>_{\sigma p}<PRE−PREPARE,v+1,n,d​null​​>​σp​​。其中 dnulld_{null}d​null​​ 是一个特定的、空请求的哈希。(空请求在系统内的处理方式和正常请求一样,但它的操作为「无操作」,不会改变状态机的状态)


    对于新的主结点 ppp,在它发送 NEW−VIEWNEW-VIEWNEW−VIEW 后,就正常进入 v+1v+1v+1 域。对于其它从结点,在收到 v+1v+1v+1 域的 <NEW−VIEW><NEW-VIEW><NEW−VIEW> 消息后,会首先检查这个消息的正确性。如果正确,才会正式进入域 v+1v+1v+1。然后无论是主结点还是从结点,都会像前面描述的正常流程一样,开始处理集合 OOO 中的所有 <PRE−PREPARE><PRE-PREPARE><PRE−PREPARE> 消息。
    从结点通过检查 <NEW−VIEW><NEW-VIEW><NEW−VIEW> 的签名、集合 VVV 和 集合 OOO 是否正确,来判断 <NEW−VIEW><NEW-VIEW><NEW−VIEW> 消息是否正确(检查集合 OOO 的方法与创建的方法一样)。
    另外,如果各结点发现自己的最新稳定检查点落后于集合 VVV 中的最新稳定检查点,那么它也会保存集合 VVV 中的最新检查点,并将其作为自己最新的检查点,丢弃旧的数据。或者如果发现自己缺少请求 mm 本身的数据(还记得请求数据和 <PRE−PREPARE><PRE-PREPARE><PRE−PREPARE> 不是放在一起传输的吗),它可以从别的结点那里获取到 mmm 数据。

    经过这三步以后,域转换就完成了,从这之后所有结点就进入了新的域时代了。
    主结点不响应前面我们提到了域转换发生的条件,其中一条就是主结点不响应客户端请求的情况。试想如果一个主结点是恶意的,但它不是通过给不同从结点发送不同消息来作恶,而是不响应客户端的请求、不将请求发送给其它从结点。如果没有一种机制来应对这种情况,那么从结点永远也不知道客户端曾经发送过请求,也就永远不会发起域转换,这个系统也就永远瘫痪了。
    处理这种情况需要客户端的配合。如果客户端发现自己发出的请求没有或很少有结点返回数据,那么客户端可以认为主结点不响应。这时客户端就会将请求广播给所有从结点。每个从结点从客户端那直接收到 <REQUEST><REQUEST><REQUEST> 请求后,并不会马上处理,而是将请求转发给主结点,并等待与这个请求对应的、主结点发送的 <PRE−PREPARE><PRE-PREPARE><PRE−PREPARE> 消息。如果在一定时间内没有收到主结点的 <PRE−PREPARE><PRE-PREPARE><PRE−PREPARE> 消息,那么从结点就认为主结点没有响应,从而发送 <VIEW−CHANGE><VIEW-CHANGE><VIEW−CHANGE> 消息,提议进行域转换;如果有足够多(2f+1)个结点提议进行域转换,就会真正进入域转换,从而将不响应的主结点换掉。
    (原论文中并没有讨论在主结点不响应时、进入域转换流程后,客户端当初广播给所有结点的请求是如何被处理的。依算法的情况来看,这个请求应该是被忽略了。客户端在发现仍然没有结点返回请求后,需要再次广播请求,直到结点们域转换完成,且换到了一个正常的结点当主结点)。
    关键问题分析前面我们详细的说明了 PBFT 算法的流程,但也只是说明了流程,很少提到为什么要这样做。这一小节里,我们就针对一些关键问题,聊一聊「为什么」。
    三阶段的作用其实 PBFT 的整个流程还是非常容易理解的(我个人认为比「拜占庭将军问题」论文里给出的方法好理解多了),但我看完这个算法的第一个反应是:为什么要分三个阶段呢?一个阶段不行吗?两个阶段不行吗?
    其实我们在之前的小节「如果我来发明这个算法」里已经提到过三阶段的原因了,但这里我们要说得更正式一些。
    首先再次提一下我自己的认识。pre-prepare 阶段,是主结点分发请求给所有从结点的阶段,这个过程必不可少,也很好理解。prepare 阶段,是各从结点「商量」达成一致的阶段,大家把自己的收到的消息公布出来,看看自己是不是属于「大多数」,如果是,理论上讲其实就可以放心的响应请求啦。commit 阶段,是确定别人的 prepare 阶段是否成功的阶段,这样就可以避免自己通过了 prepare 阶段响应了请求,而别人并没有通过 prepare 阶段、也就没有响应请求,从而造成了状态不一致的状况。
    这是我对三阶段中每阶段的作用的理解。若以原论文的描述为准,我感觉这些理解都不是很「正式」(但我自己觉得也没有错)下面我们看看原论文中的说法。
    其实仔细琢磨一下 PBFT,就会发现只要正常结点间执行请求的顺序是一致的,它们的状态就能保持一致。因此保持请求的执行顺序的一致性就很重要。而保持一致性的关键,是序号不会被重复使用,即如果某些正常结点认为请求 mmm 的序号是 nnn,那么其它正常结点就必须不能认为另一个请求 m′m^{\prime}m​′​​ 的序号是 nnn。pre-prepare 和 prepare 阶段的作用,就是在同一域内保证了这一点。比如说,在域 vvv 中,某一个或多个正常结点使用序号 nnn 来执行请求 mmm,即 prepared(m,v,n,i)prepared(m,v,n,i)prepared(m,v,n,i) 为 truetruetrue;那么可以确定,其它的正常结点一定不会使用序号 nnn 来执行另一个不同的请求 m′m^{\prime}m​′​​。
    为什么可以这么肯定呢?为了证明,我们先假设这种情况会发生,即存在一些正常结点 jjj 使用序号 nnn 执行另一个不同的请求 m′m^{\prime}m​′​​,即 prepared(m′,v,n,j)prepared(m^{\prime},v,n,j)prepared(m​′​​,v,n,j) 为 truetruetrue。根据我们前面了解的 PBFT 三阶段的算法,preparedpreparedprepared 为 truetruetrue 代表有 2f+1 个结点对某一消息的序号进行了相同的确认。这就是说,prepared(m,v,n,i)prepared(m,v,n,i)prepared(m,v,n,i) 为 truetruetrue 代表有 2f+1 个结点确认了 mmm 的序号是 nnn;prepared(m′,v,n,j)prepared(m^{\prime},v,n,j)prepared(m​′​​,v,n,j) 为 truetruetrue 代表有 2f+1 个结点确认了 m′m^{\prime}m​′​​ 的序号是 nnn。而结点的总数量为 3f+1,那么必定有 f+1 个结点对这两种情况都进行了确认。恶意结点最多有 f 个,那么对两种情况都进行了确认的 f+1 个结点中,至少有 1 个是正常结点,而这是不可能的。所以假设不成立,肯定不会存在其它正常结点使用序号 nnn 执行另一个不同的请求 m′m^{\prime}m​′​​ 的情况。
    但是正如我们所说,pre-prepare 和 prepare 仅能保证在同一域内请求顺序的共识。并不能保证跨域的情况下所有结点对请求的顺序仍能达成共识。假如某结点 iii 的 preparedpreparedprepared 函数为 truetruetrue 后立即执行了请求(即没有 commit 阶段),但其它结点的 preparedpreparedprepared 函数并不是 truetruetrue,因而它们发起了域转换,那么结果是虽然结点 iii 也被迫转到了新的域,但只有它使用序号 nnn 执行了请求 mmm ;对于新主结点来说,序号 nnn 可能还是未被分配的,所以当有新的请求时,新主结点就可能会将序号 nnn 分配给新的请求,结果就是仍然出现了我们刚才讨论的问题,即结点 iii 使用序号 nnn 执行了请求 mmm,但其它结点却使用序号 nnn 执行了新的请求 m′m^{\prime}m​′​​。
    这里你可能会说,域转换时会将 preparedpreparedprepared 为 truetruetrue 的请求 mmm 及序号 nnn 放到 <VIEW−CHANGE><VIEW-CHANGE><VIEW−CHANGE> 中啊,这样根据前面讲的域转换的流程,新的主结点就会将这个消息的 <PRE−PREPARE><PRE-PREPARE><PRE−PREPARE> 消息再广播一遍,从而使这个请求再次正常执行一遍整个流程,序号 nnn 也不会被复用了。但这里执行了请求 mmm 的结点 iii 并没有发送 <VIEW−CHANGE><VIEW-CHANGE><VIEW−CHANGE> 消息,它是被迫进行域转换的,而其它主动提议域转换的结点的 mmm 的 preparedpreparedprepared 函数并不为 truetruetrue,因此 <VIEW−CHANGE><VIEW-CHANGE><VIEW−CHANGE> 消息中并不会包含请求 mmm 及序号 nnn 等信息。
    所以为了避免上面说的情况,需要加上 commit 阶段。commit 阶段和域转换算法一起,保证了达到了 committed−localcommitted-localcommitted−local 条件的请求,即使在发生域转换以后,在新的域里各结点依然能对消息的顺序达成共识。还是考虑刚才的情况,在结点 iii 内,committed−local(m,v,n,i)committed-local(m,v,n,i)committed−local(m,v,n,i) 为 truetruetrue ,然后结点 iii 执行了这个请求。但此时其它结点 committed−localcommitted-localcommitted−local 并不是 truetruetrue(因而肯定还没有执行这个请求),而是超时发起了域转换。只要发起域转换的结点中至少有一个结点的 prepared(m,v,n,i)prepared(m,v,n,i)prepared(m,v,n,i) 为 truetruetrue,那么 <NEW−VIEW><NEW-VIEW><NEW−VIEW> 中肯定包含了消息 mmm 和序号 nnn 的 <PRE−PREPARE><PRE-PREPARE><PRE−PREPARE> 消息,因而在新的域里面会再次使用序号 nnn 执行一遍关于请求 mmm 的正常流程,此时除了刚才结点 iii 之外的结点就会仍然使用序号 nnn 执行请求 mmm,从而达到与结点 iii 一致的状态(虽然不在一个域中)。
    我们如何能确定发起域转换的结点中至少有一个结点 prepared(m,v,n,i)prepared(m,v,n,i)prepared(m,v,n,i) 为 truetruetrue 呢?一方面,结点 iii 的 committed−local(m,v,n,i)committed-local(m,v,n,i)committed−local(m,v,n,i) 已经是 truetruetrue,也就是说它肯定收到了至少 2f 条其它结点的 <COMMIT><COMMIT><COMMIT> 消息,这也说明至少有 2f 个结点的 preparedpreparedprepared 为 truetruetrue。另一方面,如果域转换想要成功,必定至少有 2f 个结点主动发送 <VIEW−CHANGE><VIEW-CHANGE><VIEW−CHANGE> 消息。总结点数量为 3f+1,所以 2f 个 preparedpreparedprepared 为 truetruetrue 的结点和 2f 个发送 <VIEW−CHANGE><VIEW-CHANGE><VIEW−CHANGE> 消息的结点中,必须有重合的。也就是说,肯定有结点它的 preparedpreparedprepared 为 truetruetrue 并且发送了 <VIEW−CHANGE><VIEW-CHANGE><VIEW−CHANGE> 消息。
    以上就是三阶段的作用的分析。总得来说,pre-prepare 和 prepare 阶段保证了在同一域内请求的执行顺序;commit 阶段和域转换规则保证了在不同域内,请求的执行顺序仍然是不变的。
    相信经过上面一段详细的说明,读者对三个阶段的作用会有更加深刻的认识。
    安全性(Safety)和活性(Liveness)之前我们在讨论 PBFT 的各个方面时,其实已经涉及到安全性和活性的问题,但没有特意指出这俩特性。在这一小节里,我们再将安全性和活性相关的问题讨论一遍。
    我们先说安全性。安全性是指系统内所有正常结点可以达成「正确的一致性」,而不会受内部恶意结点的干扰。「正确的一致性」是我自己发明的,这里不仅指达成一致的决定,而且这个决定需要是客户端的原始请求。比如客户端请求计算 10 的平方,那么各正常结点必须计算 10 的平方,而不是每个结点收到多个数值(如 10, 20, 30, …)然后计算这些数值的平均值(或中位数)的平方(拜占庭将军问题中的 SMSMSM 算法就可能会再现这种情况)。对于后一种情况,虽然每个结点最终参加计算的值和结果都是一致的,但并不是原来客户端的请求。
    由于 PBFT 系统中的所有消息都有签名,我们不用担心客户端的请求被篡改。所以只要每个正常的结点能拿到客户端的请求并只执行原始的请求,就不必担心刚才提到的后一种情况。需要重点关注的仍是如何达成一致。可以确定,只要所有正常的结点始终以同样的顺序处理请求,那么这些正常结点的状态始终是一致的,也就是达成一致了。因而总得来说,就可以保证安全性。那算法是如何保证所有正常结点以相同的顺序处理请求呢?正是前面我们刚才讨论的三阶段和域转换的作用:pre-prepare 和 prepare 可以保证在同一域内请求的执行顺序达成一致;commit 阶段和域转换规则可以保证在不同域内这一执行顺序也不会发生改变。详细信息上一小节已作了详细的说明,这里不再重复了。因此可以说,签名机制和整个 PBFT 的算法设计提供了安全性。
    不过论文中也提到一点,就是这里的安全性仅仅是指系统内部的安全性,它只能使系统内的恶意结点无法干扰正常的工作,但并不能阻止外部如客户端作恶(比如向整个系统写入垃圾数据)。
    我们再来说说活性。前面说过,所谓活性就是整个系统持续处理请求的能力。如果主结点是一个恶意结点,而没有机制可以更换这个主结点,那么这个系统就没有活性。前面我们介绍过,域转换其实就是更改主结点,因此可以说,PBFT 中的活性主要是由域转换机制保证的。具体的域转换规则前面已经详细介绍过,这里不再重复。但这里我们要说一下保证活性的三个细节。
    第一个细节,就是要避免频繁地进行域转换。这主要是通过线性增加超时时间来完成的。比如一个结点在开始处理一个请求时,它设置一个时长为 T1T_1T​1​​ 的计时器,如果计时器超时仍没有完成这个请求的 commit 阶段,那么除了发起域转换,它还会把 T1T_1T​1​​ 设置得更大一些(比如 2T12T_12T​1​​),以保证下次可以容忍更久的请求处理时间(当然也需要在请求处理得比较快的时候减小 T1T_1T​1​​,或设置 T1T_1T​1​​ 的最大值,防止超时时间无限增大);再比如一个结点为了更新到域 v+1v+1v+1 而发送 <VIEW−CHANGE><VIEW-CHANGE><VIEW−CHANGE> 消息后,设置一个时长为 T2T_2T​2​​ 的计时器,如果计时器超时仍没有收到 <NEW−VIEW><NEW-VIEW><NEW−VIEW> 消息,那么这个结点可以再次为更新到域 v+2v+2v+2 而发送 <VIEW−CHANGE><VIEW-CHANGE><VIEW−CHANGE> 消息,并这次计时器的时间间隔会设置得更大,比如 2T22T_22T​2​​。
    第二个细节,如果一个结点累计收到了超过(包含) f+1 条域编号比结点自己当前域编号大的 <VIEW−CHANGE><VIEW-CHANGE><VIEW−CHANGE> 消息,那么该结点需要立即使用这些消息中的域编号最小的编号,重新发送一遍 <VIEW−CHANGE><VIEW-CHANGE><VIEW−CHANGE> 消息。这样有助于及时的进入到新的域中。(原因如下:假设某结点 iii 收到了 f+1f+1f+1 个其它结点的 <VIEW−CHANGE><VIEW-CHANGE><VIEW−CHANGE> 消息,说明至少有一个正常结点发现了异常并发起了域转换。但若结点 iii 非常等待自己发现异常(比如共识三阶段的超时)才去发起域转换,会多浪费一些时间。反正已经可以确认有正常结点发现异常了,不如直接跟随马上发起域转换。)
    第三个细节是自然而然的,即除了恶意的主结点,其它恶意结点无法强制频繁地进行域转换。因为域转换算法规定需要有 2f+1 个结点发送 <VIEW−CHANGE><VIEW-CHANGE><VIEW−CHANGE> 消息才可能进行域转换,而系统中最多有 f 个恶意结点,显然达不到域转换成功的要求(事实上,只要发送 <VIEW−CHANGE><VIEW-CHANGE><VIEW−CHANGE> 消息的结点数量小于(不包含) f+1 ,就肯定不会进行域转换;但超过或等于 f+1 个结点发送 <VIEW−CHANGE><VIEW-CHANGE><VIEW−CHANGE> 消息,就肯定会进行域转换。因为这 f+1 个结点中,必定至少有一个正常结点,而一个正常结点一旦发送了 <VIEW−CHANGE><VIEW-CHANGE><VIEW−CHANGE> 消息,就不会处理其它消息。这会导致其它正常处理请求的结点因无法收到 2f 条 <PREPARE><PREPARE><PREPARE> 或 <COMMIT><COMMIT><COMMIT> 消息而超时,从而也发起域转换)。虽然恶意主结点可以通过不响应或发送错误消息强制发起域转换,但因为最多只有 f 个恶意结点,所以最多连续强迫系统发生 f 次域转换,这是可以接受的。
    PBFT 与 $$SM$$ 算法的比较这一小节里我们将 PBFT 与拜占庭将军问题的文章中的 SMSMSM 算法放在一起,进行一下比较,从而可以更加深刻的理解这两种算法。
    其实 PBFT 与 SMSMSM 有一定的相似性,但 PBFT 更进一步,考虑和解决了很多现实的问题,所以才可以应用于实际环境中。下面我们先聊聊它们之间的共同点,再看看 PBFT 比 SMSMSM 「更进一步」在哪些地方。
    共同点相比起不同点,PBFT 与 SMSMSM 的共同点较少,我认为主要在两个方面:一是系统模型相同,都是主从结构;二是从结点拿到主结点消息后,都会进行「沟通」与汇总。
    首先在SMSMSM 算法中,有一个司令官,其它人都是副官,接受并执行司令官的命令;而 PBFT 算法中,也分主结点和从结点,从结点也接受主结点的消息并执行。这一点上,它们是一样的。
    其次在两种算法中,所有副官(从结点)收到司令官(主结点)的消息后,都不会着急着去立刻执行,而是将自己收到的消息广播给其它结点,并接收其它结点广播的消息。这就像一个沟通的过程:我告诉别人我收到了什么消息,别人也告诉我他收到了什么消息。最终每个结点会在这些消息的基础上汇总一个结果。这一过程在 PBFT 中并不那么明显,但 prepare 阶段本质上也是这么一个过程。
    我觉得在相同点上,两种算法主要就是这两方面的相同,这两方面也都是基础。下面我们来看看在这两个基础之上的不同,这些不同点也是让 PBFT 的应用性强于 SMSMSM 的地方。
    不同点由于 PBFT 与 SMSMSM 的不同点稍多且需要较多的说明,因此我们分小节来看这些不同点。
    「一致性」与「正确的一致性」在 SMSMSM 算法中只要求一致性,即只要最终所有副官能达成一致的结果就可以了,至于这个结果是什么并不关心。比如如果司令官是叛徒,他给有的副官发送「进攻」、给有的副官发送「撤退」,只要最终忠诚的副官们行动一致,就算是正确的,不管是「一致进攻」还是「一致撤退」。
    但这在 PBFT 中是不行的。在 PBFT 中,客户端请求什么,所有结点就计算什么。如果从结点们发现彼此请求的数据不一致,它们就拒绝执行,而不是像 SMSMSM 那样取一个中间状态去执行。这就是通过对 <PRE−PREPARE><PRE-PREPARE><PRE−PREPARE> 消息的检验和必须收到 2f 条 <PREPARE><PREPARE><PREPARE> 消息这两方面来保证的。
    外部可识别正确结果在 SMSMSM 中,最终所有副官的行动肯定是一致的。但作为一个外部成员,却无法知道哪些人的行动是可信的。比如存在 5 个将军,其中只有 2 个是忠诚的,3 个是叛徒。并且司令官是忠诚的。因此在发送命令时,忠诚的司令官给每个人发送了「进攻」的命令。根据 SMSMSM 算法,另一个忠诚的副官肯定也会执行「进攻」。但另外 3 个叛徒的行为就不一定了,他们可能都执行的是「撤退」。那么在一个外人看来,你该相信哪个行动是正确的呢?
    PBFT 中的客户端其实就相当于这样一个「外人」。但与 SMSMSM 不同的是,在 PBFT 中客户端是能够知道哪些结果是正确的。这是它们之间很大的不同。
    那么 PBFT 是如何做到这一点的呢?其实主要是结点数量的差别。
    仔细研究 SMSMSM 算法就会发现,虽然 f+2 个结点也可以让正常结点(哪怕只有 2 个)达成一致,但外部(比如客户端)并不知道哪个结点的结果是正确的,正如刚才的例子显示的,如果 f>=2 且 f 个结点的结果是一致的(但是错误的),那么外部(比如客户端)是无法确定应该相信哪个结果的。比如若客户端根据「数量最多的结果就是正确的」的原则,那么它就会采用 f 个恶意结点返回的结果。这显然是不对的。因此在 PBFT 中,除了要求正确的结点达成一致外,还要有数量上的优势,让客户端知道应该采用谁的结果。所以 PBFT 要求 3f+1 个结点。由于只有 f 个恶意结点,那么客户端只要收到 f+1 个相同的结果,就可以认为这是正常的结果。
    既然只要有数量上的优势就可以,为什么 2f+1 个结点不行呢?根据 PBFT 论文中的描述,PBFT 可以用于存在恶意结点的情况,那么除了有 f 个恶意结点,还可能有 f 个正确结点「临时出点状况」,比如网络偶尔故障,因此 3f+1 个结点可以最大程序的确保整个系统正常运行。
    (事实上我对论文中这个解释是有点疑问的。客户端只要 f+1 个结点返回一样的结果,就可以认为这个结果就是正确的结果。但在系统内部处理请求的时候,每个结点仍然需要等待 2f 条 <PREPARE><PREPARE><PREPARE> 和 <COMMIT><COMMIT><COMMIT>,因此只要有 1 个正常结点「临时出点状况」,出状况其间请求是无法处理的。所以这难道不是要求所有正常结点都不能出状况吗?)
    那么 4f+1 个结点行不行呢?也不是不可以,只是这么多结点拖慢整个系统处理请求的速度,却没带来其它额外好处。
    活性是否考虑了活性,是 SMSMSM 与 PBFT 非常明显也是非常重要的区别。PBFT 考虑到了活性问题,所以它是「实用的」;而 SMSMSM 根据没有考虑更换司令官的问题,因而也就无法在实际应用中使用。
    总结PBFT 是一个比较重要的共识算法,是许多其它共识算法的基础。在这篇文章里,我们详细介绍了 PBFT 的相关知识,包括主从模式,pre-prepare / prepare / commit 三阶段及其作用,域和域转换等。pre-prepare 和 prepare 阶段让所有正常结点对请求的处理顺序达成一致;而 commit 和域转换规则保证了在发生域转换时,也能保持这个处理顺序。
    0 留言 2020-11-17 10:25:35 奖励30点积分
  • 共识算法:拜占庭将军问题


    本文原作为:fatcat22,如需转载请注明来源。原文地址:https://yangzhe.me/2019/11/06/byzantine-generals-problem/

    最近在学习区块链方面的知识,看到这篇博文讲得很好,故转载分享!
    引言接触区块链,经常会听到有人提到「拜占庭将军问题」(The Byzantine Generals Problem),所以这篇文章里,我们就详细探讨一下这个「问题」。
    本篇文章的讨论多数来自于「拜占庭将军问题」的原始论文,有一些细节参考了网上这篇文章。
    什么是拜占庭将军问题「拜占庭将军问题」来源于这样一个场景:
    拜占庭帝国的军队正在围攻一座城市,这支军队被分成了多支小分队,驻扎在城市周围的不同方位,每支小分队由一个将军领导。这些将军们彼此之间只能依靠信使传递消息(无法聚在一起开个会)。每个将军在观察自己方位的敌情以后,会给出一个各自的行动建议(比如进攻、撤退或按兵不动),但最终的需要将军们达成一致的作战计划并共同执行,否则就会被敌人各个击破。但是,这些将军中可能有叛徒,他们会尝试阻止其他忠诚的将军达成一致的作战计划。
    这就是拜占庭将军的「问题」:只能依靠通信相互交流,又不知道谁是叛徒,怎么能不受叛徒们的影响,让这些忠诚的将军快速的达到一致的作战计划呢?
    很显然,将这一场景套用到计算机系统中也是非常适用的:在一个分布式系统中,针对每个运算,每台独立的机器也需要最终达成一致的结果。但每台计算机之间也只能依靠网络通信(显然它们无法聚在一起开会),每台计算机都有出错的可能(被攻击,或故障),从而变成「叛徒」干扰正常的计算机达成一致。
    这一问题是由 Leslie·Lamport 等人在这篇论文中提出的,并在论文中给出了理论可行的解决方案和证明。不过在学习这些解决方案之前,我们还要对「拜占庭将军问题」作进一步的推导,看一下解决方案只要符合哪些要求,就能解决拜占庭将军问题。
    推导根据刚才的描述可以总结出,忠诚的将军们使用的算法,需要保证以下两点:

    A:所有忠诚的将军可以达成一致的作战计划
    B:少数的叛徒不会导致忠诚的将军们无法达成一致

    (论文中第二条本来是「少数的叛徒不会导致忠诚的将军们采用错误的计划」(A small number of traitors cannot cause the loyal generals to adopt a bad plan),并在接下来对什么是「bad plan」作了一个间接的解释,我的理解是,在这里只要是不一致的行动计划,都是「bad plan」,无论是「进攻」还是「撤退」)
    如果我们假设 v(i)v(i)v(i) 为第 iii 个将军的作战计划,且每个将军使用某种方法将序列 v(1),v(2),..,v(n)v(1),v(2),..,v(n)v(1),v(2),..,v(n) 转换成一个单一的作战计划。那么只要所有的将军使用相同的方法转换 v(1),v(2),..,v(n)v(1),v(2),..,v(n)v(1),v(2),..,v(n) ,条件A就可以被满足。条件B可以通过某种更有弹性的方法来满足,比如获取到消息序列 v(1),v(2),..,v(n)v(1),v(2),..,v(n)v(1),v(2),..,v(n) 以后,通过投票的方式,少数服从多数,得出一个最终的、一致的作战计划。
    问题似乎很简单就被解决了,但我们忽略了一点,想要满足上面两个条件,所有忠诚的将军必须拿到同样的「v(1),v(2),..,v(n) v(1),v(2),..,v(n)v(1),v(2),..,v(n) 」。而叛徒可能给不同的将军发送不同的消息,使这些将军拿到的是不同的消息序列,这种情况下我们刚才的解决方法就无法成立了。所以我们必须想办法保证:
    1. 所有忠诚的将军必须拿到相同的消息序列 v(1),v(2),..,v(n)v(1),v(2),..,v(n)v(1),v(2),..,v(n)
    只要某个算法能保证条件1,那么条件A和条件B也是可以保证的,因而这个算法就可以解决将军们的问题。
    那么如何保证条件1呢?有些将军(叛徒)可能给不同的将军发送不同的值,而要使所有忠诚的将军拿到相同的消息序列,这些忠诚的将军们就不能直接使用自己接收到的值。也就是说,将军们最终使用的 v(i)v(i)v(i) 不一定就是将军 iii 当初发送的原始值,即使将军 iii 是一个忠诚的将军。为什么这么说呢?因为如果让将军们必须直接使用其它将军发送的原始值,那么由于叛徒会给不同将军发送不同值,所以条件1永远也无法达成。所以对于叛徒发出的值,将军们不能直接使用。但将军们无法区分谁是叛徒谁是忠诚的,所以如果不多加注意,就会导致抛弃或修改某个忠诚的将军发出原始值的情况。但这显然是不对的,对于忠诚的将军,我们应该必须使用他发出的原始值,所以我们必须保证:
    2. 如果将军 iii 是忠诚的,那么它发出的原始值 v(i)v(i)v(i) 必须被其他忠诚的将军所采用
    条件2只提到了「如果将军 iii 是忠诚的」的情况,如果将军 iii 是叛徒呢?根据条件1,我们依然要保证所有忠诚的将军拿到相同的值。所以我们可以得出:
    1’. 对于任意一个将军 iii,无论他是忠诚的还是叛徒,当他发出值时,所有的忠诚的将军都将采用相同的值,即 v(i)v(i)v(i)(虽然可能不是将军 iii 发送的原始值)
    至此,只要某个算法能保证条件1’(对任意一个将军发出的值,其他忠诚的将军都将使用相同的值),就能保证条件1(所有忠诚的将军肯定会拿到相同的消息序列)。再加上条件2(忠诚的将军发出的原始值肯定会被其它忠诚的将军采用),就可以保证条件A和条件B的成立,因而这个算法就可以解决将军们的问题。
    注意条件2和条件1’考虑的都是单个的将军发送的值的情况,而只要这两个条件成立,我们就可以保证解决将军们的问题。因此我们将问题的关键转移到了「单个的将军如何发送他的值给其它人」上来。我们把这一问题表达为「司令官发送命令给他的副官们」,得到了如下拜占庭将军问题:

    拜占庭将军问题:一位司令官必须发送命令给他的 n - 1 个副官们,且满足条件:IC1. 所有忠诚的副官获得相同的命令IC2. 如果司令官是忠诚的,那么所有忠诚的副官都会获得司令官发出的原始命令

    这里 IC1 对应着条件1’; IC2 对应着条件2,不同的是 IC2 特别强调了「司令官」,而条件2只说「对任意一个将军」。后面我们会看到,司令官是会轮换的,任意一个将军都可能成为司令官,所以这两个说明其实是一样的。
    至此,我们得出了确定性的拜占庭将军问题的定义。只要能保证 IC1 和 IC2,就可以解决将军们的问题。
    (这里可能会有人疑惑:IC1 和 IC2 到底是「问题」,还是「解决条件」。我觉得「问题」和「解决条件」是一致的。它们构成了问题,也是解决问题的关键,解决了它们,就解决了问题)
    解决方案的不可能性介绍完拜占庭将军问题以后,你可能会觉得其实也挺简单。不过论文中也提出了「解决方案的不可能性」(IMPOSSIBILITY RESULTS),指出在某些条件下,将军们无论如何是无法达成一致的。我们需要先对这个作一个介绍,然后再去介绍解决方案。
    我们这里先说结论:在使用口头消息的情况下,不存在将军总数小于 3m+13m+13m+1 的解决方案,能够在存在 mmm 个叛徒的情况下解决拜占庭将军问题。也就是说,如果有 mmm 个叛徒,则至少需要 3m+13m+13m+1 个将军,才能让忠诚的将军们达成一致。
    什么是口头消息呢?所谓口头消息,是指内容完全由发送者或转发者控制的消息。将军们使用这种消息传递信息时,叛徒可以修改自己收到的任意消息,再转发给其人,而其它人无法识别出这个消息是否被修改过。(与口头消息对应的是签名消息,即消息是经过原始发送者签名的,收到消息的人可以根据签名验证此消息是否被修改过)
    下面我们简单证明一下这个结论。首先来证明最简单的情况,即当叛徒数量 m=1 时,不存在将军总数 <= 3 的解决方案,可以解决拜占庭将军问题。下面这张图我直接截取自原始论文:

    我们先来看 Fig.1 代表的第一种情况。此时司令官是忠诚的,2号副官是叛徒。司令官给所有副官发送了「attack」命令,但副官2是叛徒,所以他欺骗副官1自己收到了「retreat」命令。因为副官1也不知道谁是叛徒,所以此时副官1会很迷茫,不知道谁说的是真的:如果他相信副官2,那么他将不会与忠诚的司令官达成一致;如果他相信司令官,倒是暂时正确了,但事情还未结束。
    我们再来看 Fig.2 代表的第二种情况。此时司令官是叛徒,两个副官是忠诚的。司令官给不同的副官发送了不同的命令,副官2也如实将司令官的命令发给了副官1。但此时副官1依然会迷茫,因为他仍然收到了两个不同的命令。可以看到,对于副官1来说,当前收到的消息与刚才第一种情况下收到的消息是一样的,他依然不知道该相信谁。在第一种情况里,选择相信司令官是暂时正确的,但在当前的情况里却是错误的。
    所以结合这两种情况来看,无论副官1选择相信谁,都有可能是错误的。所以可以得出结论,在只有一个叛徒但将军总量 <= 3 的情况下,无法保证忠诚的将军们达成一致。
    现在我们再来看叛徒数量 m>1 的情况。m>1 时论文的证明很有意思,它将 m=1 时的每一位将军想象成同类将军的代表,比如在 Fig.1 中,司令官和副官1分别代表 m 个忠诚的将军,副官2代表 m 个叛徒;在 Fig.2 中,司令官代表 m 个叛徒,副官1和副官2分别代表 m 个忠诚的将军。因此也可以得出, m>1 但将军总量 <= 3m 时,无法保证忠诚的将军们达成一致。
    以上就是这一「解决方案的不可能性」的证明过程。但我总是感觉这个证明有些「玄乎」,感觉能理解,但好像又不是真的可以理解。论文中也提到了类似的问题,然后将严谨的证明过程指向了另一篇论文。不过我们不是作学术研究,就不继续追究下去了。

    在这里谈下我自己的理解:为什么n>3f?(n是节点总数,f是恶意节点)
    我们要在收到n-f条消息的时候,就必须做出决定,因为若有f个节点可以不发消息,这时节点最多能接收到n-f条消息。所以,我们必须要在接收到n-f条消息时做出决定。
    当在通信网络中,节点接收到n-f条消息时,最坏的情况是未接收到的消息都是诚实节点发的,而接收到的消息中有f条消息正好是恶意节点发的,那么这时要想做出少数服从多数的正确决定,诚实节点消息必须多于恶意节点消息:(n-f)-f>f。

    口头消息的解决方案刚才我们介绍了不可能存在解决方案的情况,那么现在我们就来介绍一下,存在解决方案的时,如何解决拜占庭将军问题。
    在这一小节里我们假设将军们使用「口头消息」(Oral Message)传递消息。前面我们已经介绍过,所谓口头消息,是指内容完全由发送者或转发者控制的消息。将军们使用这种消息传递信息时,叛徒可以修改自己收到的任意消息,再转发给其人,而其它人无法识别出这个消息是否被修改过。另外,我们还要对将军们的消息传递系统作如下的限制:

    A1. 每一个消息都可以在两个将军间正确的传递,传递过程中不会被修改
    A2. 消息的接收者知道这个消息的真正发送者是谁
    A3. 消息的缺失是能够被将军们发现的

    A1 和 A2 可以防止叛徒干扰两个将军之间的通信:A1 让叛徒无法在通信过程中修改信息;A2 让叛徒无法冒充其它将军发送消息。A3 可以防止叛徒通过不发消息的方式影响一致共识的达成。并且如果将军们发现缺少某个消息,他们可以使用统一的默认值(比如 RETREAT)来替代缺失的消息。
    另外,我们还假设每个将军都可以直接发消息给其它任意一个将军,不需要中间有人代理转发。
    下面我们先给出算法的定义,然后再详细解释一下算法过程。
    我们首先要定义一个函数 majoritymajoritymajority,这个函数有这样的功能:如果大多数的 viv_iv​i​​ 等于 vvv,那么 majority(v1,..,vn−1)=v majority(v_1,..,v_{n-1}) = v majority(v​1​​,..,v​n−1​​)=v。比如可以这样实现这个函数:

    1.majoritymajoritymajority 函数可以取出现次数最多的那个值,否则为一个默认值(如 RETREAT)
    2.majoritymajoritymajority 函数可以取所有值的中位数(如果这些值可以排序的话)

    我们定义使用口头消息解决拜占庭将军问题的算法为OM(m)OM(m)OM(m),其中 mmm 代表叛徒的数量且 m>=0m>=0m>=0,nnn 代表将军的总数量且 n>=3m+1n>=3m+1n>=3m+1。 OM(m)OM(m)OM(m) 算法如下:
    OM(0)OM(0)OM(0):

    司令官把他的值发送给每一位副官
    每一位副官使用从司令官那里接收到的值作为共识值。如果没接收到任何值则使用默认值作为共识值

    OM(m),m>0OM(m),m>0OM(m),m>0:

    司令官把它的值发送给每一位副官。对于每一个副官 iii,假设 viv_iv​i​​ 为自己从司令官那里接收到的值(如果没接收到则为默认值)
    每一个副官 iii 作为新的司令官、其它所有副官(当然不包含自己和当前司令官啦)作为新的副官,执行算法 OM(m−1) OM(m-1) OM(m−1)。(在算法 OM(m−1)OM(m-1)OM(m−1) 中新司令官 iii 会将他接收到的值 viv_iv​i​​ 发送他的副官们)
    假设 vi′v^{\prime}_iv​i​′​​ 为第二步中的副官们对第二步中的新司令官 iii 发送的值达成的共识值,则当前副官们的共识值为 majority(v1′,v2′,..,vn−1′) majority(v^{\prime}_1, v^{\prime}_2,.. ,v^{\prime}_{n-1}) majority(v​1​′​​,v​2​′​​,..,v​n−1​′​​)

    这里我们要马上解释一下 共识值 这个概念(这个词是我自己创造的,原论文中没有)。所谓「共识值」,是指副官们一致认同的司令官发送的值。这里的关键是并不是司令官发什么值,副官们就接受并相信什么值;而是副官之间要对司令官发送的值进行「探讨」,最终形成一个一致意见,接受并相信一个相同的值,这个值就是「共识值」。如果司令官是叛徒,那么这个值不一定就是司令官发出的原始值。比如有 4 个将军,司令官是叛徒,他给其他 3 个副官发送的值分别是 a、b、c。那么 3 个副官最终的共识值应该是 majority(a,b,c)majority(a,b,c)majority(a,b,c)。
    OM(m)OM(m)OM(m) 算法使用了递归,这使它非常难以理解。但我们这里先不详细考虑算法本身的流程,而是从更高一层的角度想想,为什么会产生拜占庭将军问题,以及应该怎样应对。
    产生拜占庭将军问题的原因我认为是:每个忠诚的将军不知道谁是叛徒,从而产生了对其他将军的不信任。
    那怎么应对呢?既然是不知道该相信谁且多数将军是忠诚的,那么只能使用 majoritymajoritymajority 函数产生一个「多数人的意见」,并服从这个意见。所以当副官们接收到司令官的命令时,副官们不知道司令官是不是叛徒,从而不能轻易相信司令官,只能依然副官们「相互沟通」后,达成一个可以相信的「共识值」。
    副官们沟通的方法就是将司令官排除出去,每个副官将自己接收到的值发给其他所有人,这样每个副官就能知道司令官发给所有人值了。然后副官们就使用 majoritymajoritymajority 函数从这些值中计算出一个「共识值」。
    但问题是,在这些沟通的副官中,仍可能会有叛徒,他发出来的值可能根本不是从司令官接收到的值,且可能发给其他每个人的值都不一样,这样每个忠诚的副官拿到的就不是一样的序列 v1,..,vn−1v_1,..,v_{n-1}v​1​​,..,v​n−1​​,还是没法达成一致的。
    其实在副官们的「沟通」过程中,每当一位副官向其他人发送自己的值时,其他人也不知道这位副官是否是叛徒,因此也不应该直接相信他,而是应该所有接收他消息的人再次「相互沟通」,以便对这位副官发送的值达成共识。这里就产生了递归:每一位副官向其他人发送自己接收到的值时,也可以看作自己是「司令官」,其他人是自己的副官。其他的副官在彩纳自己发送的值之前,首先要充分的「相互沟通」达成一个共识值。
    以上基本上就是 OM(m)OM(m)OM(m) 算法的要素和递归过程。这么来看,这个算法的逻辑就比较容易理解了。
    那什么时候递归结束呢?或者说,什么时候可以相信司令官发送的值,而不用再「相互沟通」了呢。在 OM(m)OM(m)OM(m) 算法中,每递归一轮,mmm 的值就减 1,当m=0m=0m=0 时,副官们就不用再「相互沟通」了,而是直接将司令官发送的值作为当前的共识值。至于为什么这样是正确的,我们一会再来说明。
    下面我们通过实例,来加深对这一算法的理解。首先看一看论文中比较简单的 m=1m=1m=1 时的例子。
    首先看司令官是忠诚的情况,此时有一个副官是叛徒:

    从图中可以看到,在 OM(1) 的第 (1) 步中,司令官开始给每个副官发送一个值,本例中司令官是忠诚的,所以他给每个副官的值都是一样的,为 a。
    在 OM(1) 的第 (2) 步中,每个副官各自作为司令官,进入到 OM(m−1)OM(m-1)OM(m−1) 算法中,将自己收到的值发给其他副官。此时 m=0m=0m=0,所以其它副官把此时自己收到的值作为这一层次的共识值。这一步执行完以后,每个副官都会收到其它两个副官发送的值,再加上自己在第 (1) 步中收到的值,此时每个副官共收到了 3 个值。然后进入到下一步中。
    在 OM(1) 的第 (3) 步中,每个副官利用 majoritymajoritymajority 函数,计算自己收到的 3 个值。由于 L1 自己从 L0 那里收到了一个 a 值;且在 OM(0) 中从 L2 那里收到的也是 a 值,从 L3 那里收到的是 x,所以 L1 的共识值应该是 a。L2 的情况与 L1 类似,他的共识值也是 a。所以 L0、L1、L2 三个忠诚的将军达成了一致,他们的共识值都是 a。
    我们再来看看司令官是叛徒的情况;

    此时在 OM(1) 的第 (1) 步中,由于司令官 L0 是叛徒,所以他可能发给每个人的值都不一样(以尽最大可能达到干优忠诚将军们的目的),所以我们假设 L1、L2、L3 收到的值各不相同,分别为 a、b、c。
    下面的步骤与刚才类似,我们不再赘述。总之 L1、L2、L3 分别收到了除自己这外的其他两个副官发送的值,所以他们最后每个人收到的三个值其实都是 a、b、c。当他们使用 majoritymajoritymajority 函数计算共识值时,由于输入值是相同的,所以输出的肯定是同一个值。因此最终三个忠诚的将军仍然达成了一致的共识值 t,虽然这个值可能与司令官 L0 发送的值完全不一样。
    m=1m=1m=1 时 OM(m)OM(m)OM(m) 算法很简单,也很容易理解。以此为预热,我们来看一下复杂一些的情况,比如 m=3m=3m=3 时,OM(3)OM(3)OM(3) 是如何执行的。我们下面的示意图使用的图例与刚才完全一致,只是更复杂而已。由于 OM(3)OM(3)OM(3) 的情况实在太复杂,如果全部用图示意出来,图片会非常的大,也会非常复杂,这样反而失去了图片示意的意义。因此在下面这张图中,每一个步骤我只示意了第一种情况和最后一种情况,其它情况都用省略号代替了。另外在乍用这张图理解 OM(3)OM(3)OM(3) 算法时,建议先纵向看,即先沿着某一分支一直向下看,看明白了再看其它分支。最后再横向综合起来看。
    另外,也由于 OM(3)OM(3)OM(3) 太复杂,所以这里也只示意了叛徒作为司令官的情况。忠诚将军作为司令官的情况是类似的(甚至会更简单些)。
    下面就是 OM(3)OM(3)OM(3) 的示意图(如果图片太小,可以尝试点击图片看大图,或在新标签中打开图片,或图片另存为本地图片后查看):

    虽然整个过程变复杂了,但细节上与刚才介绍的 OM(1)OM(1)OM(1) 是相同的,因此就不每一步都说明介绍了。需要特别提出来的是,在 OM(1)OM(1)OM(1) step (1) 中、L9 作为司令官时,最终忠诚的将军们是无法对 L9 发送的信息达成一致的共识值的(OM(1)OM(1)OM(1) step (3) 中),但这并不妨碍忠诚将军们达到最终的一致共识。
    与前面介绍过的 OM(1)OM(1)OM(1) 中判徒作为司令官的情况类似,这里忠诚将军们虽然最终达成了一致(上图中用值 C 表示),但这个值可能与最开始司令官发出来的值不一样。
    在原论文中还给出了这个算法的正确性证明。这里我们就不进行证明了,只是聊一下证明相关的思路,以及为什么当 m=0 时各将军就不再相互确认,而是直接将接收到的值作为当前的共识值。由于在 OMOMOM 算法中,每进行一轮都会忽略当前司令官、剩下的副官们相互发送消息确认。那么我们设想两个极端的情况:

    第一种情况是每次忽略的都是叛徒
    第二种情况是每次忽略的都是忠诚将军

    在第一种情况下,每次忽略的都是叛徒,因此当最后 m=0 时,一共忽略了 m 个叛徒,但总共也就 m 个叛徒。也就是说,在这种情况下当最后 m=0 时,剩下的所有将军都是忠诚的,因此他们肯定可以达成一致的共识值。
    在第二种情况下,每次忽略的都是忠诚将军,因此最后当 m=0 时,一共忽略了 m 个忠诚将军,此时剩下的将军中,有 m 个是叛徒,有 m+1 个是忠诚将军。忠诚将军的数量大于叛徒的数量,因此还是可以达成一致的共识值的。
    因此无论哪种情况下,在 OM(1)OM(1)OM(1) 的第 (3) 步中,忠诚将军们肯定是可以达成一致共识的。论文中证明的关键也是无论什么时候,忠诚将军的数量总是多于叛徒的。
    签名消息的解决方案回看一下口头消息的解决方案,还是很复杂的。其实口头消息的解决方案之所以复杂,就是因为叛徒可以随意改更忠诚将军的消息,而别人无法发现消息被改。如果我们让忠诚将军的消息无法篡改,那么问题就变得简单多了。这就是签名消息的解决方案。
    前面介绍口头消息时,我们对将军们之间的消息传递系统作了一些限制(前面的 A1 - A3)。在使用签名消息时,我们要在之前限制的基础上,再加一条:

    A4.(a) 忠诚将军的签名是无法被修改的;任何改动包含了忠诚将军签名的消息的行为,都可以被发现(b) 任意一个人都可以验证属于某将军的签名是不是真的是他自己签的

    注意这里我们并没有对叛徒的签名作任何的限制。我们可以允许叛徒之间相互修改和伪造彼此的签名,而不被别人发现。
    既然我们现在使用了消息签名,那么之前将军数量必须大于等于 3m+13m+13m+1 才能达成共识的限制就可以去除了。事实上,我们可以让任何数量的将军团体在存在 mmm 个叛徒的情况下达成共识(这里虽然说任意数量,但如果总数小于 m+2m+2m+2 将没有意义。因为「达成共识」意味着两个或两个以上的人,只有一个忠诚将军或跟本没有忠诚将军谈不上「达成共识」)。
    在给出解决方案之前,我们首先要定义一个函数 choicechoicechoice。这个函数输入一个值的集合,输出一个单一值。我们对这个函数有两个要求:

    一是如果集合 VVV 由单个元素 vvv 组成,那么 choice(v)=vchoice(v)=vchoice(v)=v
    二是 choice(∅)choice(\varnothing)choice(∅) 始终为相同的默认值,比如 RETREAT。共中 ∅\varnothing∅ 代表集合为空

    另外在算法中,我们使用 x:ix:ix:i 代表由将军 iii 签名的值 xxx。类似的 v:j:iv:j:iv:j:i 代表值 vvv 先由将军 jjj 签名得到 v:jv:jv:j,然后 v:jv:jv:j 又被将军 iii 签名,得到 v:j:iv:j:iv:j:i。
    我们定义使用签名消息解决拜占庭将军问题的算法为 SM(m)SM(m)SM(m),其中 mmm 代表叛徒的数量且 m>=0m>=0m>=0。 SM(m)SM(m)SM(m) 算法如下:

    (0). 每个将军 i 初始化自己的值集合 Vi=∅V_i=\varnothingV​i​​=∅
    (1). 司令官将要发送的值签名,然后发送签名后的值
    (2). 对于每个副官 iii:

    (A) 如果副官 iii 之前没接收过任何将军发过来的任何值,且值的形式是 v:0v:0v:0,那么:

    (i) 将 vvv 加入到 ViV_iV​i​​ 中(此时 V=vV=vV=v)
    (ii) 将 v:0:iv:0:iv:0:i 发送给其他副官

    (B) 如果副官 iii 接收到了一个形式如 v:0:j1:..:jkv:0:j_1:..:j_kv:0:j​1​​:..:j​k​​ 这样的值,并且 vvv 不在 ViV_iV​i​​ 中,那么:

    (i) 将 vvv 加入到 ViV_iV​i​​ 中
    (ii) 如果 k<mk<mk<m,那么此副官将值 v:0:j1:..:jk:iv:0:j_1:..:j_k:iv:0:j​1​​:..:j​k​​:i 发送给除 j1,..,jkj_1,..,j_kj​1​​,..,j​k​​ 之外的所有其它副官

    (C) 如果副官 iii 接收到一个已经存在于 ViV_iV​i​​ 中的值,则忽略它

    (3). 对于每个副官 iii,当自己不会再接收到更多值的时候,它将 choice(Vi)choice(V_i)choice(V​i​​) 作为最终自己的共识值

    (论文中解释了第 (3) 步中如判断自己不会再接收到更多的值,但我觉得不太靠谱。这里只是算法,不是实现,所以就姑且认为可以判断吧)
    可以看到,SMSMSM 算法要比 OMOMOM 算法详细、简单,尤其是 SMSMSM 算法没有用到递归来解决问题。注意在第 (2) 步中,(A)、(B)、(C) 三种情况是互斥的,即只要执行了某一情况,就不会再去执行另一情况。可以把第 (2) 步理解成编程语言中的 switch/case 语句。
    这个算法的关键是维护一个集合 VVV,如果新收到的值不在这个集合中,就将它加入进去,并对这个值签名后再将其发送给其他人;如果已存在于集合中,就忽略不管了。 仔细理解这一过程你就会发现,SMSMSM 的关键思想是通过消息不可篡改这一特性,让所有忠诚将军成为「一体」,就像同一个人一样。 当某个值第一次被忠诚将军接收到时,无论是第 (2) 步的 情况 (A) 还是 情况 (B),这个忠诚将军都会将这个值发送给其他所有没给这个值签过名的人;由于签名值的不可篡改,最终其他所有忠诚将军的集合 ViV_iV​i​​ 中肯定也会存在这个值。因此除非消息到达不了忠诚将军那里,只要到达,就会「全体忠诚将军都有」。这样看来,无论叛徒怎么干扰,都无济于事了,因为最终忠诚将军们的集合 ViV_iV​i​​ 肯定都是一样的,因此 choicechoicechoice 最终的结果也肯定是一样的。所不同的是,如果司令官是忠诚的,那么最终所有忠诚将军的集合 ViV_iV​i​​ 中肯定只有一个值,就是司令官原始发送的值;而如果司令官是叛徒,他给不同的副官发送了不同的值,那么最终所有忠诚将军的集合 ViV_iV​i​​ 中会有多个值(但整个集合还是相等的)。
    这里还要解释一下为什么在算法的 (2)(B)(ii) 步骤中,只有 k<mk<mk<m 的情况下,才会将值签名后,发给其他副官。因为接收到的值 v:0:j_1:..:j_kv:0:j\_1:..:j\_kv:0:j_1:..:j_k 有 k+1k+1k+1 个签名(注意最前面还有编号为 0 的司令官的签名)。如果 k>=mk>=mk>=m,那么 k+1>=m+1k+1>=m+1k+1>=m+1,即当 k>=mk>=mk>=m 时,至少有 m+1m+1m+1 个将军对这个值签过名了,而这 m+1m+1m+1 个将军中至少有 1 个忠诚的将军。也就是说当 k>=mk>=mk>=m 时至少有 1 个忠诚的将军的集合 VVV 中已经有这个值了。刚才我们说过,忠诚的将军们是「一体的」,只要有一个忠诚的将军有这个值了,其它忠诚将军也肯定会有这个值。所以当 k>=mk>=mk>=m 时就没必要再给别人发送这个值了。
    SMSMSM 算法比较容易理解,所以我们这里只看一下论文中给出的简单例子即可。论文中的例子中总共有 3 个将军,其中有 1 个叛徒,并且司令官就是这个叛徒(注意这个例子并不需要如 OMOMOM 算法那样需要 4 个将军才能达成共识)。如下图(图片来自原论文):

    在上图中,叛徒司令官给两个副官分别发送了不同的值。副官1收到值后发现这是自己第一次收到值且是司令官发来的,于是执行步骤 (2)(A),将 “attack” 加入到了自己的集合 V1V_1V​1​​ 中,然后将 “attack”:0:1 发送给副官2;类似的副官 2 在收到司令官发来的值后,也将 “retreat” 加入到自己的集合 V2V_2V​2​​ 中,然后将 “retreat”:0:2 发送给副官1。
    副官1接收到副官2发来的消息后,发现自己的集合中没有 “retreat” 这个值,因此他将这个值加入到了自己的集合 V1V_1V​1​​ 中。此时副官1的集合为 “attack”,“retreat”。
    副官2接收到副官1发来的消息后,也发现自己的集合中没有 “attack” 这个值,因此他也将这个值加入到了自己的集合 V2V_2V​2​​ 中。此时副官2的集合为 “retreat”,“attack”。
    最后我们可以看到,两个忠诚的副官的集合都是一样的。因此 choice(V1)choice(V_1)choice(V​1​​) 和 choice(V2)choice(V_2)choice(V​2​​) 的值也肯定是一样的(不管这个值是什么)。所以最终忠诚的将军达成了共识。
    总结通过这篇文章,我们详细了解了什么是拜占庭将军问题,以及原论文给出的基于口头消息和签名消息的解决方法。「拜占庭将军问题」是区块链共识的一个基础(我觉得也是各种分布式系统的共识的基础),了解了这个问题,有利于我们以后理解其它很多的共识算法。
    拜占庭将军问题的原论文虽然给出了基于口头消息和签名消息的解决方案,但这些方案并不能很好的应用于实际生产环境中(比如基于口头消息的方法,通信量太大;基于签名消息的方法,如果司令官一直是叛徒,那这个系统虽然可以达成一致,但也干不了什么正事)。因此很多前辈和大牛给出了不少其他可实际应用的解决方案,我们以后的文章会继续学习这些方案。
    0 留言 2020-08-30 14:12:54 奖励30点积分
  • 以太坊智能合约 OPCODE 逆向之理论基础篇


    本文由 Seebug Paper 发布,如需转载请注明来源。本文地址:https://paper.seebug.org/640/

    最近在学习 solidity 逆向方面的知识,看到这篇博文讲得很好,故转载分享!
    一、基础二、IO2.1 stack2.2 mem2.3 storage三、变量3.1 全局变量的储存模型3.1.1 定长变量3.1.2 映射变量3.1.3 变长变量3.1.4 结构体四、函数4.1 两种调用函数的方式4.2 调用函数4.3 主函数中的函数4.4 回退函数和payable4.5 函数参数4.6 变量类型的分辨五、智能合约代码结构5.1 部署合约5.2 创建合约代码总结附录(操作码对应含义和GAS)Ethereum VM (EVM) Opcodes and Instruction ReferenceNotesTableInstruction DetailsADDPUSHXCALL在我们对etherscan等平台上合约进行安全审查时,常常会遇到没有公布Solidity源代码的合约,只能获取到合约的OPCODE,所以一个智能合约的反编译器对审计无源码的智能合约起到了非常重要的作用。
    目前在互联网上常见的反编译工具只有porosity[1],另外在Github上还找到另外的反编译工具ethdasm[2],经过测试发现这两个编译器都有许多bug,无法满足我的工作需求。因此我开始尝试研究并开发能满足我们自己需求的反编译工具,在我看来如果要写出一个优秀的反汇编工具,首先需要有较强的OPCODE逆向能力,本篇Paper将对以太坊智能合约OPCODE的数据结构进行一次深入分析。
    一、基础智能合约的OPCODE是在EVM(Ethereum Virtual Machine)中进行解释执行,OPCODE为1字节,从0x00 - 0xff代表了相对应的指令,但实际有用的指令并没有0xff个,还有一部分未被使用,以便将来的扩展。
    具体指令可参考Github[3]上的OPCODE指令集,每个指令具体含义可以参考相关文档[4]。
    二、IO在EVM中不存在寄存器,也没有网络IO相关的指令,只存在对栈(stack)、内存(mem)、存储(storage)的读写操作。
    2.1 stack使用的push和pop对栈进行存取操作,push后面会带上存入栈数据的长度,最小为1字节,最大为32字节,所以OPCODE从0x60-0x7f分别代表的是push1-push32。
    PUSH1会将OPCODE后面1字节的数据放入栈中,比如字节码是0x6060代表的指令就是PUSH1 0x60。
    除了PUSH指令,其他指令获取参数都是从栈中获取,指令返回的结果也是直接存入栈中。
    2.2 mem内存的存取操作是MSTORE和MLOAD:

    MSTORE(arg0, arg1)从栈中获取两个参数,表示MEM[arg0:arg0+32] = arg1
    MLOAD(arg0)从栈中获取一个参数,表示PUSH32(MEM[arg0:arg0+32])

    因为PUSH指令,最大只能把32字节的数据存入栈中,所以对内存的操作每次只能操作32字节。
    但是还有一个指令MSTORE8,只修改内存的1个字节。

    MSTORE(arg0, arg1)从栈中获取两个参数,表示MEM[arg0] = arg1
    内存的作用一般是用来存储返回值,或者某些指令有处理大于32字节数据的需求。
    比如: SHA3(arg0, arg1)从栈中获取两个参数,表示SHA3(MEM[arg0:arg0+arg1]),SHA3对内存中的数据进行计算sha3哈希值,参数只是用来指定内存的范围。
    2.3 storage上面的stack和mem都是在EVM执行OPCODE的时候初始化,但是storage是存在于区块链中,我们可以类比为计算机的存储磁盘。
    所以,就算不执行智能合约,我们也能获取智能合约storage中的数据:
    eth.getStorageAt(合约地址, slot) # 该函数还有第三个参数,默认为"latest",还可以设置为"earliest"或者"pending",具体作用本文不做分析
    storage用来存储智能合约中所有的全局变量,使用SLOAD和SSTORE进行操作:

    SSTORE(arg0, arg1)从栈中获取两个参数,表示eth.getStorageAt(合约地址, arg0) = arg1
    SLOAD(arg0)从栈中获取一个参数,表示PUSH32(eth.getStorageAt(合约地址, arg0))

    三、变量智能合约的变量从作用域可以分为三种:全局公有变量(public)、全局私有变量(private)和局部变量。

    全局变量和局部变量的区别:全局变量储存在storage中,而局部变量是被编译进OPCODE中,在运行时,被放在stack中,等待后续使用
    公有变量和私有变量的区别:公有变量会被编译成一个constant函数,后面会分析函数之前的区别

    因为私有变量也是储存在storage中,而storage是存在于区块链当中,所以相当于私有变量也是公开的,所以不要想着用私有变量来储存啥不能公开的数据。
    3.1 全局变量的储存模型不同类型的变量在storage中储存的方式也是有区别的,下面对各种类型的变量的储存模型进行分析。
    solidity内存地址结构

    3.1.1 定长变量第一种我们归类为定长变量,所谓的定长变量,也就是该变量在定义的时候,其长度就已经被限制住了。
    比如定长整型(int/uint……)、地址(address)、定长浮点型(fixed/ufixed……)、定长字节数组(bytes1-32)。
    这类的变量在storage中都是按顺序储存:
    uint a; // slot = 0address b; // 1ufixed c; // 2bytes32 d; // 3## a == eth.getStorageAt(contract, 0)d == eth.getStorageAt(contract, 3)
    上面举的例子,除了address的长度是160bits,其他变量的长度都是256bits,而storage是256bits对齐的,所以都是一个变量占着一块storage,但是会存在连续两个变量的长度不足256bits的情况:
    address a; // slot = 0uint8 b; // 0address c; // 1uint16 d; // 1
    在opcode层面:

    获取a的值得操作是:SLOAD(0) & 0xffffffffffffffffffffffffffffffffffffffff
    获取b值得操作是:SLOAD(0) // 0x10000000000000000000000000000000000000000 & 0xff
    获取d值得操作是: SLOAD(1) // 0x10000000000000000000000000000000000000000 & 0xffff

    因为b的长度+a的长度不足256bits,变量a和b是连续的,所以他们在同一块storage中,然后在编译的过程中进行区分变量a和变量b,但是后续在加上变量c,长度就超过了256bits,因此把变量c放到下一块storage中,然后变量d跟在c之后。
    从上面我们可以看出,storage的储存策略一个是256bits对齐,一个是顺序储存。(并没有考虑到充分利用每一字节的储存空间,我觉得可以考虑把d变量放到b变量之后)。
    3.1.2 映射变量mapping(address => uint) a;
    映射变量就没办法想上面的定长变量按顺序储存了,因为这是一个键值对变量,EVM采用的机制是:
    SLOAD(sha3(key.rjust(64, "0")+slot.rjust(64, "0")))
    比如: a["0xd25ed029c093e56bc8911a07c46545000cbf37c6"]首先计算sha3哈希值:
    >>> from sha3 import keccak_256>>> data = "d25ed029c093e56bc8911a07c46545000cbf37c6".rjust(64, "0")>>> data += "00".rjust(64, "0")>>> keccak_256(data.encode()).hexdigest()'739cc24910ff41b372fbcb2294933bdc3108bd86ffd915d64d569c68a85121ec'# a["0xd25ed029c093e56bc8911a07c46545000cbf37c6"] == SLOAD("739cc24910ff41b372fbcb2294933bdc3108bd86ffd915d64d569c68a85121ec")
    我们也可以使用以太坊客户端直接获取:
    > eth.getStorageAt(合约地址, "739cc24910ff41b372fbcb2294933bdc3108bd86ffd915d64d569c68a85121ec")
    还有slot需要注意一下:
    address public a; // slot = 0mapping(address => uint) public b; // slot = 1uint public d; // slot = 1mapping(address => uint) public c; // slot = 3
    根据映射变量的储存模型,或许我们真的可以在智能合约中隐藏私密信息,比如,有一个secret,只有知道key的人才能知道secret的内容,我们可以b[key] = secret, 虽然数据仍然是储存在storage中,但是在不知道key的情况下却无法获取到secret。
    不过,storage是存在于区块链之中,目前我猜测是通过智能合约可以映射到对应的storage,storage不可能会初始化256*256bits的内存空间,那样就太消耗硬盘空间了,所以可以通过解析区块链文件,获取到storage全部的数据。
    上面这些仅仅是个人猜想,会作为之后研究以太坊源码的一个研究方向。
    3.1.3 变长变量变长变量也就是数组,长度不一定,其储存方式有点像上面两种的结合
    uint a; // slot = 0uint[] b; // 1uint c; // 2
    数组任然会占用对应slot的storage,储存数组的长度(b.length == SLOAD(1))。
    比如我们想获取b[1]的值,会把输入的index和SLOAD(1)的值进行比较,防止数组越界访问。
    然后计算slot的sha3哈希值:
    >>> from sha3 import keccak_256>>> slot = "01".rjust(64, "0")>>> keccak_256(slot.encode()).hexdigest()'20ec45d096f1fa2aeff1e3da8a84697d90109524958ed4be9f6d69e37a9140a4'#b[X] == SLOAD('20ec45d096f1fa2aeff1e3da8a84697d90109524958ed4be9f6d69e37a9140a4' + X)# 获取b[2]的值> eth.getStorageAt(合约地址, "20ec45d096f1fa2aeff1e3da8a84697d90109524958ed4be9f6d69e37a9140a6")
    在变长变量中有两个特例:string和bytes。
    字符串可以认为是字符数组,bytes是byte数组,当这两种变量的长度在0-31时,值储存在对应slot的storage上,最后一字节为长度*2|flag, 当flag = 1,表示长度>31,否则长度<=31
    下面进行举例说明:
    uint i; // slot = 0string a = "c"*31; // 1SLOAD(1) == "c*31" + "00" | 31*2 == "636363636363636363636363636363636363636363636363636363636363633e"
    当变量的长度大于31时,SLOAD(slot)储存length*2|flag,把值储存到sha3(slot):
    uint i; // slot = 0string a = "c"*36; // 1SLOAD(1) == 36*2|1 == 0x49SLOAD(SHA3("01".rjust(64, "0"))) == "c"*36
    3.1.4 结构体结构体没有单独特殊的储存模型,结构体相当于变量数组,下面进行举例说明:
    struct test { uint a; uint b; uint c;}address g;Test e;// 上面变量在storage的储存方式等同于address g;uint a;uint b;uint c;
    四、函数4.1 两种调用函数的方式下面是针对两种函数调用方式说明的测试代码,发布在测试网络上: https://ropsten.etherscan.io/address/0xc9fbe313dc1d6a1c542edca21d1104c338676ffd#code
    pragma solidity ^0.4.18;contract Test { address public owner; uint public prize; function Test() { owner = msg.sender; } function test1() constant public returns (address) { return owner; } function test2(uint p) public { prize += p; }}
    整个OPCODE都是在EVM中执行,所以第一个调用函数的方式就是使用EVM进行执行OPCODE:
    # 调用test1> eth.call({to: "0xc9fbe313dc1d6a1c542edca21d1104c338676ffd", data: "0x6b59084d"})"0x0000000000000000000000000109dea8b64d87a26e7fe9af6400375099c78fdd"> eth.getStorageAt("0xc9fbe313dc1d6a1c542edca21d1104c338676ffd", 0)"0x0000000000000000000000000109dea8b64d87a26e7fe9af6400375099c78fdd"
    第二种方式就是通过发送交易:
    # 调用test2> eth.getStorageAt("0xc9fbe313dc1d6a1c542edca21d1104c338676ffd", 1)"0x0000000000000000000000000000000000000000000000000000000000000005"> eth.sendTransaction({from: eth.accounts[0], to: "0xc9fbe313dc1d6a1c542edca21d1104c338676ffd", data: "0xcaf446830000000000000000000000000000000000000000000000000000000000000005"})> eth.getStorageAt("0xc9fbe313dc1d6a1c542edca21d1104c338676ffd", 1)"0x000000000000000000000000000000000000000000000000000000000000000a"
    这两种调用方式的区别有两个:

    使用call调用函数是在本地使用EVM执行合约的OPCODE,所以可以获得返回值
    通过交易调用的函数,能修改区块链上的storage

    一个调用合约函数的交易(比如 https://ropsten.etherscan.io/tx/0xab1040ff9b04f8fc13b12057f9c090e0a9348b7d3e7b4bb09523819e575cf651)的信息中,是不存在返回值的信息,但是却可以修改storage的信息(一个交易是怎么修改对应的storage信息,是之后的一个研究方向)。
    而通过call调用,是在本地使用EVM执行OPCODE,返回值是存在MEM中return,所以可以获取到返回值,虽然也可以修改storage的数据,不过只是修改你本地数据,不通过发起交易,其他节点将不会接受你的更改,所以是一个无效的修改,同时,本地调用函数也不需要消耗gas,所以上面举例中,在调用信息的字典里,不需要from字段,而交易却需要指定(设置from)从哪个账号消耗gas。
    4.2 调用函数EVM是怎么判断调用哪个函数的呢?下面使用OPCODE来进行说明。
    每一个智能合约入口代码是有固定模式的,我们可以称为智能合约的主函数,上面测试合约的主函数如下:
    PS: Github[5]上面有一个EVM反汇编的IDA插件。
    [ 0x0] | PUSH1 | ['0x80'][ 0x2] | PUSH1 | ['0x40'][ 0x4] | MSTORE | None[ 0x5] | PUSH1 | ['0x4'][ 0x7] | CALLDATASIZE | None[ 0x8] | LT | None[ 0x9] | PUSH2 | ['0x61'][ 0xc] | JUMPI | None[ 0xd] | PUSH4 | ['0xffffffff'][ 0x12] | PUSH29 | ['0x100000000000000000000000000000000000000000000000000000000'][ 0x30] | PUSH1 | ['0x0'][ 0x32] | CALLDATALOAD | None[ 0x33] | DIV | None[ 0x34] | AND | None[ 0x35] | PUSH4 | ['0x6b59084d'][ 0x3a] | DUP2 | None[ 0x3b] | EQ | None[ 0x3c] | PUSH2 | ['0x66'][ 0x3f] | JUMPI | None[ 0x40] | DUP1 | None[ 0x41] | PUSH4 | ['0x8da5cb5b'][ 0x46] | EQ | None[ 0x47] | PUSH2 | ['0xa4'][ 0x4a] | JUMPI | None[ 0x4b] | DUP1 | None[ 0x4c] | PUSH4 | ['0xcaf44683'][ 0x51] | EQ | None[ 0x52] | PUSH2 | ['0xb9'][ 0x55] | JUMPI | None[ 0x56] | DUP1 | None[ 0x57] | PUSH4 | ['0xe3ac5d26'][ 0x5c] | EQ | None[ 0x5d] | PUSH2 | ['0xd3'][ 0x60] | JUMPI | None[ 0x61] | JUMPDEST | None[ 0x62] | PUSH1 | ['0x0'][ 0x64] | DUP1 | None[ 0x65] | REVERT | None
    反编译出来的代码就是:
    def main(): if CALLDATASIZE >= 4: data = CALLDATA[:4] if data == 0x6b59084d: test1() elif data == 0x8da5cb5b: owner() elif data == 0xcaf44683: test2() elif data == 0xe3ac5d26: prize() else: pass raise
    PS:因为个人习惯问题,反编译最终输出没有选择对应的Solidity代码,而是使用Python。
    从上面的代码我们就能看出来,EVM是根据CALLDATA的前4字节来确定调用的函数的,这4个字节表示的是函数的sha3哈希值的前4字节:
    > web3.sha3("test1()")"0x6b59084dfb7dcf1c687dd12ad5778be120c9121b21ef90a32ff73565a36c9cd3"> web3.sha3("owner()")"0x8da5cb5b36e7f68c1d2e56001220cdbdd3ba2616072f718acfda4a06441a807d"> web3.sha3("prize()")"0xe3ac5d2656091dd8f25e87b604175717f3442b1e2af8ecd1b1f708bab76d9a91"# 如果该函数有参数,则需要加上各个参数的类型> web3.sha3("test2(uint256)")"0xcaf446833eef44593b83316414b79e98fec092b78e4c1287e6968774e0283444"
    所以可以去网上找个哈希表映射[6],这样有概率可以通过hash值,得到函数名和参数信息,减小逆向的难度。
    4.3 主函数中的函数上面给出的测试智能合约中只有两个函数,但是反编译出来的主函数中,却有4个函数调用,其中两个是公有函数,另两个是公有变量。
    智能合约变量/函数类型只有两种,公有和私有,公有和私有的区别很简单,公有的是能别外部调用访问,私有的只能被本身调用访问。
    对于变量,不管是公有还是私有都能通过getStorageAt访问,但是这是属于以太坊层面的,在智能合约层面,把公有变量给编译成了一个公有函数,在这公有函数中返回SLOAD(slot),而私有函数只能在其他函数中特定的地方调用SLOAD(slot)来访问。
    在上面测试的智能合约中, test1()函数等同于owner(),我们可以来看看各自的OPCODE:
    ; test1(); 0x66: loc_66[ 0x66] | JUMPDEST | None[ 0x67] | CALLVALUE | None[ 0x68] | DUP1 | None[ 0x69] | ISZERO | None[ 0x6a] | PUSH2 | ['0x72'][ 0x6d] | JUMPI | None[ 0x6e] | PUSH1 | ['0x0'][ 0x70] | DUP1 | None[ 0x71] | REVERT | None; 0x72: loc_72[ 0x72] | JUMPDEST | None[ 0x73] | POP | None[ 0x74] | PUSH2 | ['0x7b'][ 0x77] | PUSH2 | ['0xfa'][ 0x7a] | JUMP | None; 0xFA: loc_fa[ 0xfa] | JUMPDEST | None[ 0xfb] | PUSH1 | ['0x0'][ 0xfd] | SLOAD | None[ 0xfe] | PUSH20 | ['0xffffffffffffffffffffffffffffffffffffffff'][ 0x113] | AND | None[ 0x114] | SWAP1 | None[ 0x115] | JUMP | None; 0x7B: loc_7b[ 0x7b] | JUMPDEST | None[ 0x7c] | PUSH1 | ['0x40'][ 0x7e] | DUP1 | None[ 0x7f] | MLOAD | None[ 0x80] | PUSH20 | ['0xffffffffffffffffffffffffffffffffffffffff'][ 0x95] | SWAP1 | None[ 0x96] | SWAP3 | None[ 0x97] | AND | None[ 0x98] | DUP3 | None[ 0x99] | MSTORE | None[ 0x9a] | MLOAD | None[ 0x9b] | SWAP1 | None[ 0x9c] | DUP2 | None[ 0x9d] | SWAP1 | None[ 0x9e] | SUB | None[ 0x9f] | PUSH1 | ['0x20'][ 0xa1] | ADD | None[ 0xa2] | SWAP1 | None[ 0xa3] | RETURN | None
    和owner()函数进行对比:
    ; owner(); 0xA4: loc_a4[ 0xa4] | JUMPDEST | None[ 0xa5] | CALLVALUE | None[ 0xa6] | DUP1 | None[ 0xa7] | ISZERO | None[ 0xa8] | PUSH2 | ['0xb0'][ 0xab] | JUMPI | None[ 0xac] | PUSH1 | ['0x0'][ 0xae] | DUP1 | None[ 0xaf] | REVERT | None; 0xB0: loc_b0[ 0xb0] | JUMPDEST | None[ 0xb1] | POP | None[ 0xb2] | PUSH2 | ['0x7b'][ 0xb5] | PUSH2 | ['0x116'][ 0xb8] | JUMP | None; 0x116: loc_116[ 0x116] | JUMPDEST | None[ 0x117] | PUSH1 | ['0x0'][ 0x119] | SLOAD | None[ 0x11a] | PUSH20 | ['0xffffffffffffffffffffffffffffffffffffffff'][ 0x12f] | AND | None[ 0x130] | DUP2 | None[ 0x131] | JUMP | None; 0x7B: loc_7b[ 0x7b] | JUMPDEST | None[ 0x7c] | PUSH1 | ['0x40'][ 0x7e] | DUP1 | None[ 0x7f] | MLOAD | None[ 0x80] | PUSH20 | ['0xffffffffffffffffffffffffffffffffffffffff'][ 0x95] | SWAP1 | None[ 0x96] | SWAP3 | None[ 0x97] | AND | None[ 0x98] | DUP3 | None[ 0x99] | MSTORE | None[ 0x9a] | MLOAD | None[ 0x9b] | SWAP1 | None[ 0x9c] | DUP2 | None[ 0x9d] | SWAP1 | None[ 0x9e] | SUB | None[ 0x9f] | PUSH1 | ['0x20'][ 0xa1] | ADD | None[ 0xa2] | SWAP1 | None[ 0xa3] | RETURN | None
    所以我们可以得出结论:
    address public a;会被编译成(==)function a() public returns (address) { return a;}#address private a;function c() public returns (address) { return a;}等同于下面的变量定义(≈)address public c;
    公有函数和私有函数的区别也很简单,公有函数会被编译进主函数中,能通过CALLDATA进行调用,而私有函数则只能在其他公有函数中进行调用,无法直接通过设置CALLDATA来调用私有函数。
    4.4 回退函数和payable在智能合约中,函数都能设置一个payable,还有一个特殊的回退函数,下面用实例来介绍回退函数。
    比如之前的测试合约加上了回退函数:
    function() { prize += 1;}则主函数的反编译代码就变成了:
    def main(): if CALLDATASIZE >= 4: data = CALLDATA[:4] if data == 0x6b59084d: return test1() elif data == 0x8da5cb5b: return owner() elif data == 0xcaf44683: return test2() elif data == 0xe3ac5d26: return prize() assert msg.value == 0 prize += 1 exit()当CALLDATA和该合约中的函数匹配失败时,将会从抛异常,表示执行失败退出,变成调用回退函数。
    每一个函数,包括回退函数都可以加一个关键字: payable,表示可以给该函数转帐,从OPCODE层面讲,没有payable关键字的函数比有payable的函数多了一段代码:
    JUMPDEST | NoneCALLVALUE | NoneDUP1 | NoneISZERO | NonePUSH2 | ['0x8e']JUMPI | NonePUSH1 | ['0x0']DUP1 | NoneREVERT | None
    反编译成python,就是:
    assert msg.value == 0
    REVERT是异常退出指令,当交易的金额大于0时,则异常退出,交易失败。
    4.5 函数参数函数获取数据的方式只有两种,一个是从storage中获取数据,另一个就是接受用户传参,当函数hash表匹配成功时,我们可以知道该函数的参数个数,和各个参数的类型,但是当hash表匹配失败时,我们仍然可以获取该函数参数的个数,因为获取参数和主函数、payable检查一样,在OPCODE层面也有固定模型:
    比如上面的测试合约,调动test2函数的固定模型就是:main -> payable check -> get args -> 执行函数代码。
    获取参数的OPCODE如下:
    ; 0xAF: loc_af[ 0xaf] | JUMPDEST | None[ 0xb0] | POP | None[ 0xb1] | PUSH2 | ['0xd1'][ 0xb4] | PUSH20 | ['0xffffffffffffffffffffffffffffffffffffffff'][ 0xc9] | PUSH1 | ['0x4'][ 0xcb] | CALLDATALOAD | None[ 0xcc] | AND | None[ 0xcd] | PUSH2 | ['0x18f'][ 0xd0] | JUMP | None

    函数test2的参数p = CALLDATA[4:4+0x20]
    如果有第二个参数,则是arg2 = CALLDATA[4+0x20:4+0x40],以此类推

    所以智能合约中,调用函数的规则就是data = sha3(func_name)[:4] + *args。
    但是,上面的规则仅限于定长类型的参数,如果参数是string这种不定长的变量类型时,固定模型仍然不变,但是在从calldata获取数据的方法,变得不同了,定长的变量是通过调用CALLDATALOAD,把值存入栈中,而string类型的变量,因为长度不定,会超过256bits的原因,使用的是calldatacopy把参数存入MEM。
    可以看看function test3(string a) public {}函数获取参数的代码:
    ; 0xB2: loc_b2[ 0xb2] | JUMPDEST | None[ 0xb3] | POP | None[ 0xb4] | PUSH1 | ['0x40'][ 0xb6] | DUP1 | None[ 0xb7] | MLOAD | None[ 0xb8] | PUSH1 | ['0x20'][ 0xba] | PUSH1 | ['0x4'][ 0xbc] | DUP1 | None[ 0xbd] | CALLDATALOAD | None[ 0xbe] | DUP1 | None[ 0xbf] | DUP3 | None[ 0xc0] | ADD | None[ 0xc1] | CALLDATALOAD | None[ 0xc2] | PUSH1 | ['0x1f'][ 0xc4] | DUP2 | None[ 0xc5] | ADD | None[ 0xc6] | DUP5 | None[ 0xc7] | SWAP1 | None[ 0xc8] | DIV | None[ 0xc9] | DUP5 | None[ 0xca] | MUL | None[ 0xcb] | DUP6 | None[ 0xcc] | ADD | None[ 0xcd] | DUP5 | None[ 0xce] | ADD | None[ 0xcf] | SWAP1 | None[ 0xd0] | SWAP6 | None[ 0xd1] | MSTORE | None[ 0xd2] | DUP5 | None[ 0xd3] | DUP5 | None[ 0xd4] | MSTORE | None[ 0xd5] | PUSH2 | ['0xff'][ 0xd8] | SWAP5 | None[ 0xd9] | CALLDATASIZE | None[ 0xda] | SWAP5 | None[ 0xdb] | SWAP3 | None[ 0xdc] | SWAP4 | None[ 0xdd] | PUSH1 | ['0x24'][ 0xdf] | SWAP4 | None[ 0xe0] | SWAP3 | None[ 0xe1] | DUP5 | None[ 0xe2] | ADD | None[ 0xe3] | SWAP2 | None[ 0xe4] | SWAP1 | None[ 0xe5] | DUP2 | None[ 0xe6] | SWAP1 | None[ 0xe7] | DUP5 | None[ 0xe8] | ADD | None[ 0xe9] | DUP4 | None[ 0xea] | DUP3 | None[ 0xeb] | DUP1 | None[ 0xec] | DUP3 | None[ 0xed] | DUP5 | None[ 0xee] | CALLDATACOPY | None[ 0xef] | POP | None[ 0xf0] | SWAP5 | None[ 0xf1] | SWAP8 | None[ 0xf2] | POP | None[ 0xf3] | PUSH2 | ['0x166'][ 0xf6] | SWAP7 | None[ 0xf7] | POP | None[ 0xf8] | POP | None[ 0xf9] | POP | None[ 0xfa] | POP | None[ 0xfb] | POP | None[ 0xfc] | POP | None[ 0xfd] | POP | None[ 0xfe] | JUMP | None
    传入的变长参数是一个结构体:
    struct string_arg { uint offset; uint length; string data;}
    offset+4表示的是当前参数的length的偏移,length为data的长度,data就是用户输入的字符串数据。
    当有多个变长参数时: function test3(string a, string b) public {}。
    calldata的格式如下: sha3(func)[:4] + a.offset + b.offset + a.length + a.data + b.length + b.data
    翻译成py代码如下:
    def test3(): offset = data[4:0x24] length = data[offset+4:offset+4+0x20] a = data[offset+4+0x20:length] offset = data[0x24:0x24+0x20] length = data[offset+4:offset+4+0x20] b = data[offset+4+0x20:length]
    因为参数有固定的模型,因此就算没有从hash表中匹配到函数名,也可以判断出函数参数的个数,但是要想知道变量类型,只能区分出定长、变长变量,具体是uint还是address,则需要从函数代码,变量的使用中进行判断。
    4.6 变量类型的分辨在智能合约的OPCDOE中,变量也是有特征的。
    比如一个address变量总会 & 0xffffffffffffffffffffffffffffffffffffffff:
    PUSH1 | ['0x0']SLOAD | NonePUSH20 | ['0xffffffffffffffffffffffffffffffffffffffff']AND | None
    上一篇说的mapping和array的储存模型,可以根据SHA3的计算方式知道是映射变量还是数组变量。
    再比如,uint变量因为等同于uint256,所以使用SLOAD获取以后不会再进行AND计算,但是uint8却会计算& 0xff。
    所以我们可以SLOAD指令的参数和后面紧跟的计算,来判断出变量类型。
    五、智能合约代码结构5.1 部署合约在区块链上,要同步/发布任何信息,都是通过发送交易来进行的,用之前的测试合约来举例,合约地址为:0xc9fbe313dc1d6a1c542edca21d1104c338676ffd,创建合约的交易地址为::0x6cf9d5fe298c7e1b84f4805adddba43e7ffc8d8ffe658b4c3708f42ed94d90ed。
    查看下该交易的相关信息:
    > eth.getTransaction("0x6cf9d5fe298c7e1b84f4805adddba43e7ffc8d8ffe658b4c3708f42ed94d90ed"){ blockHash: "0x7f684a294f39e16ba1e82a3b6d2fc3a1e82ef023b5fb52261f9a89d831a24ed5", blockNumber: 3607048, from: "0x0109dea8b64d87a26e7fe9af6400375099c78fdd", gas: 171331, gasPrice: 1000000000, hash: "0x6cf9d5fe298c7e1b84f4805adddba43e7ffc8d8ffe658b4c3708f42ed94d90ed", input: "0x608060405234801561001057600080fd5b5060008054600160a060020a0319163317905561016f806100326000396000f3006080604052600436106100615763ffffffff7c01000000000000000000000000000000000000000000000000000000006000350416636b59084d81146100665780638da5cb5b146100a4578063caf44683146100b9578063e3ac5d26146100d3575b600080fd5b34801561007257600080fd5b5061007b6100fa565b6040805173ffffffffffffffffffffffffffffffffffffffff9092168252519081900360200190f35b3480156100b057600080fd5b5061007b610116565b3480156100c557600080fd5b506100d1600435610132565b005b3480156100df57600080fd5b506100e861013d565b60408051918252519081900360200190f35b60005473ffffffffffffffffffffffffffffffffffffffff1690565b60005473ffffffffffffffffffffffffffffffffffffffff1681565b600180549091019055565b600154815600a165627a7a7230582040d052fef9322403cb3c1de27683a42a845e091972de4c264134dd575b14ee4e0029", nonce: 228, r: "0xa08f0cd907207af4de54f9f63f3c9a959c3e960ef56f7900d205648edbd848c6", s: "0x5bb99e4ab9fe76371e4d67a30208aeac558b2989a6c783d08b979239c8221a88", to: null, transactionIndex: 4, v: "0x2a", value: 0}
    我们可以看出来,想一个空目标发送OPCODE的交易就是创建合约的交易,但是在交易信息中,却不包含合约地址,那么合约地址是怎么得到的呢?
    function addressFrom(address _origin, uint _nonce) public pure returns (address) { if(_nonce == 0x00) return address(keccak256(byte(0xd6), byte(0x94), _origin, byte(0x80))); if(_nonce <= 0x7f) return address(keccak256(byte(0xd6), byte(0x94), _origin, byte(_nonce))); if(_nonce <= 0xff) return address(keccak256(byte(0xd7), byte(0x94), _origin, byte(0x81), uint8(_nonce))); if(_nonce <= 0xffff) return address(keccak256(byte(0xd8), byte(0x94), _origin, byte(0x82), uint16(_nonce))); if(_nonce <= 0xffffff) return address(keccak256(byte(0xd9), byte(0x94), _origin, byte(0x83), uint24(_nonce))); return address(keccak256(byte(0xda), byte(0x94), _origin, byte(0x84), uint32(_nonce))); // more than 2^32 nonces not realistic }
    智能合约的地址由创建合约的账号和nonce决定,nonce用来记录用户发送的交易个数,在每个交易中都有该字段,现在根据上面的信息来计算下合约地址:
    # 创建合约的账号 from: "0x0109dea8b64d87a26e7fe9af6400375099c78fdd",# nonce: 228 = 0xe4 => 0x7f < 0xe4 < 0xff>>> sha3.keccak_256(binascii.unhexlify("d7" + "94" + "0109dea8b64d87a26e7fe9af6400375099c78fdd" + "81e4")).hexdigest()[-40:]'c9fbe313dc1d6a1c542edca21d1104c338676ffd'
    5.2 创建合约代码一个智能合约的OPCODE分为两种,一个是编译器编译好后的创建合约代码,还是合约部署好以后runtime代码,之前我们看的,研究的都是runtime代码,现在来看看创建合约代码,创建合约代码可以在创建合约交易的input数据总获取,上面已经把数据粘贴出来了,反汇编出指令如下:
    ; 0x0: main[ 0x0] | PUSH1 | ['0x80'][ 0x2] | PUSH1 | ['0x40'][ 0x4] | MSTORE | None[ 0x5] | CALLVALUE | None[ 0x6] | DUP1 | None[ 0x7] | ISZERO | None[ 0x8] | PUSH2 | ['0x10'][ 0xb] | JUMPI | None[ 0xc] | PUSH1 | ['0x0'][ 0xe] | DUP1 | None[ 0xf] | REVERT | None----------------------------------------------------------------; 0x10: loc_10[ 0x10] | JUMPDEST | None[ 0x11] | POP | None[ 0x12] | PUSH1 | ['0x0'][ 0x14] | DUP1 | None[ 0x15] | SLOAD | None[ 0x16] | PUSH1 | ['0x1'][ 0x18] | PUSH1 | ['0xa0'][ 0x1a] | PUSH1 | ['0x2'][ 0x1c] | EXP | None[ 0x1d] | SUB | None[ 0x1e] | NOT | None[ 0x1f] | AND | None[ 0x20] | CALLER | None[ 0x21] | OR | None[ 0x22] | SWAP1 | None[ 0x23] | SSTORE | None[ 0x24] | PUSH2 | ['0x24f'][ 0x27] | DUP1 | None[ 0x28] | PUSH2 | ['0x32'][ 0x2b] | PUSH1 | ['0x0'][ 0x2d] | CODECOPY | None[ 0x2e] | PUSH1 | ['0x0'][ 0x30] | RETURN | None
    代码逻辑很简单,就是执行了合约的构造函数,并且返回了合约的runtime代码,该合约的构造函数为:
    function Test() { owner = msg.sender;}

    因为没有payable关键字,所以开头是一个check代码assert msg.value == 0
    然后就是对owner变量的赋值,当执行完构造函数后,就是把runtime代码复制到内存中:
    CODECOPY(0, 0x32, 0x24f) # mem[0:0+0x24f] = CODE[0x32:0x32+0x24f]
    最后在把runtime代码返回: return mem[0:0x24f]

    在完全了解合约是如何部署的之后,也许可以写一个OPCODE混淆的CTF逆向题。
    总结通过了解EVM的数据结构模型,不仅可以加快对OPCODE的逆向速度,对于编写反编译脚本也有非常大的帮助,可以对反编译出来的代码进行优化,使得更加接近源码。
    附录(操作码对应含义和GAS)Ethereum VM (EVM) Opcodes and Instruction ReferenceThis reference consolidates EVM opcode information from the yellow paper, stack exchange, solidity source, parity source, evm-opcode-gas-costs and Manticore.
    New issues and contributions are welcome, and are covered by bounties from Trail of Bits. Join us in #ethereum on the Empire Hacking Slack to discuss Ethereum security tool development.
    NotesThe size of a “word” in EVM is 256 bits.
    The gas information is a work in progress. If an asterisk is in the Gas column, the base cost is shown but may vary based on the opcode arguments.
    Table


    Opcode
    Name
    Description
    Extra Info
    Gas




    0x00
    STOP
    Halts execution
    -
    0


    0x01
    ADD
    Addition operation
    -
    3


    0x02
    MUL
    Multiplication operation
    -
    5


    0x03
    SUB
    Subtraction operation
    -
    3


    0x04
    DIV
    Integer division operation
    -
    5


    0x05
    SDIV
    Signed integer division operation (truncated)
    -
    5


    0x06
    MOD
    Modulo remainder operation
    -
    5


    0x07
    SMOD
    Signed modulo remainder operation
    -
    5


    0x08
    ADDMOD
    Modulo addition operation
    -
    8


    0x09
    MULMOD
    Modulo multiplication operation
    -
    8


    0x0a
    EXP
    Exponential operation
    -
    10*


    0x0b
    SIGNEXTEND
    Extend length of two’s complement signed integer
    -
    5


    0x0c - 0x0f
    Unused
    Unused
    -


    0x10
    LT
    Less-than comparison
    -
    3


    0x11
    GT
    Greater-than comparison
    -
    3


    0x12
    SLT
    Signed less-than comparison
    -
    3


    0x13
    SGT
    Signed greater-than comparison
    -
    3


    0x14
    EQ
    Equality comparison
    -
    3


    0x15
    ISZERO
    Simple not operator
    -
    3


    0x16
    AND
    Bitwise AND operation
    -
    3


    0x17
    OR
    Bitwise OR operation
    -
    3


    0x18
    XOR
    Bitwise XOR operation
    -
    3


    0x19
    NOT
    Bitwise NOT operation
    -
    3


    0x1a
    BYTE
    Retrieve single byte from word
    -
    3


    0x1b
    SHL
    Shift Left
    EIP145
    3


    0x1c
    SHR
    Logical Shift Right
    EIP145
    3


    0x1d
    SAR
    Arithmetic Shift Right
    EIP145
    3


    0x20
    KECCAK256
    Compute Keccak-256 hash
    -
    30*


    0x21 - 0x2f
    Unused
    Unused


    0x30
    ADDRESS
    Get address of currently executing account
    -
    2


    0x31
    BALANCE
    Get balance of the given account
    -
    400


    0x32
    ORIGIN
    Get execution origination address
    -
    2


    0x33
    CALLER
    Get caller address
    -
    2


    0x34
    CALLVALUE
    Get deposited value by the instruction/transaction responsible for this execution
    -
    2


    0x35
    CALLDATALOAD
    Get input data of current environment
    -
    3


    0x36
    CALLDATASIZE
    Get size of input data in current environment
    -
    2*


    0x37
    CALLDATACOPY
    Copy input data in current environment to memory
    -
    3


    0x38
    CODESIZE
    Get size of code running in current environment
    -
    2


    0x39
    CODECOPY
    Copy code running in current environment to memory
    -
    3*


    0x3a
    GASPRICE
    Get price of gas in current environment
    -
    2


    0x3b
    EXTCODESIZE
    Get size of an account’s code
    -
    700


    0x3c
    EXTCODECOPY
    Copy an account’s code to memory
    -
    700*


    0x3d
    RETURNDATASIZE
    Pushes the size of the return data buffer onto the stack
    EIP 211
    2


    0x3e
    RETURNDATACOPY
    Copies data from the return data buffer to memory
    EIP 211
    3


    0x3f
    EXTCODEHASH
    Returns the keccak256 hash of a contract’s code
    EIP 1052
    700


    0x40
    BLOCKHASH
    Get the hash of one of the 256 most recent complete blocks
    -
    20


    0x41
    COINBASE
    Get the block’s beneficiary address
    -
    2


    0x42
    TIMESTAMP
    Get the block’s timestamp
    -
    2


    0x43
    NUMBER
    Get the block’s number
    -
    2


    0x44
    DIFFICULTY
    Get the block’s difficulty
    -
    2


    0x45
    GASLIMIT
    Get the block’s gas limit
    -
    2


    0x46
    CHAINID
    Returns the current chain’s EIP-155 unique identifier
    EIP 1344
    2


    0x47 - 0x4f
    Unused
    -


    0x50
    POP
    Remove word from stack
    -
    2


    0x51
    MLOAD
    Load word from memory
    -
    3*


    0x52
    MSTORE
    Save word to memory
    -
    3*


    0x53
    MSTORE8
    Save byte to memory
    -
    3


    0x54
    SLOAD
    Load word from storage
    -
    200


    0x55
    SSTORE
    Save word to storage
    -
    20000**


    0x56
    JUMP
    Alter the program counter
    -
    8


    0x57
    JUMPI
    Conditionally alter the program counter
    -
    10


    0x58
    GETPC
    Get the value of the program counter prior to the increment
    -
    2


    0x59
    MSIZE
    Get the size of active memory in bytes
    -
    2


    0x5a
    GAS
    Get the amount of available gas, including the corresponding reduction the amount of available gas
    -
    2


    0x5b
    JUMPDEST
    Mark a valid destination for jumps
    -
    1


    0x5c - 0x5f
    Unused
    -


    0x60
    PUSH1
    Place 1 byte item on stack
    -
    3


    0x61
    PUSH2
    Place 2-byte item on stack
    -
    3


    0x62
    PUSH3
    Place 3-byte item on stack
    -
    3


    0x63
    PUSH4
    Place 4-byte item on stack
    -
    3


    0x64
    PUSH5
    Place 5-byte item on stack
    -
    3


    0x65
    PUSH6
    Place 6-byte item on stack
    -
    3


    0x66
    PUSH7
    Place 7-byte item on stack
    -
    3


    0x67
    PUSH8
    Place 8-byte item on stack
    -
    3


    0x68
    PUSH9
    Place 9-byte item on stack
    -
    3


    0x69
    PUSH10
    Place 10-byte item on stack
    -
    3


    0x6a
    PUSH11
    Place 11-byte item on stack
    -
    3


    0x6b
    PUSH12
    Place 12-byte item on stack
    -
    3


    0x6c
    PUSH13
    Place 13-byte item on stack
    -
    3


    0x6d
    PUSH14
    Place 14-byte item on stack
    -
    3


    0x6e
    PUSH15
    Place 15-byte item on stack
    -
    3


    0x6f
    PUSH16
    Place 16-byte item on stack
    -
    3


    0x70
    PUSH17
    Place 17-byte item on stack
    -
    3


    0x71
    PUSH18
    Place 18-byte item on stack
    -
    3


    0x72
    PUSH19
    Place 19-byte item on stack
    -
    3


    0x73
    PUSH20
    Place 20-byte item on stack
    -
    3


    0x74
    PUSH21
    Place 21-byte item on stack
    -
    3


    0x75
    PUSH22
    Place 22-byte item on stack
    -
    3


    0x76
    PUSH23
    Place 23-byte item on stack
    -
    3


    0x77
    PUSH24
    Place 24-byte item on stack
    -
    3


    0x78
    PUSH25
    Place 25-byte item on stack
    -
    3


    0x79
    PUSH26
    Place 26-byte item on stack
    -
    3


    0x7a
    PUSH27
    Place 27-byte item on stack
    -
    3


    0x7b
    PUSH28
    Place 28-byte item on stack
    -
    3


    0x7c
    PUSH29
    Place 29-byte item on stack
    -
    3


    0x7d
    PUSH30
    Place 30-byte item on stack
    -
    3


    0x7e
    PUSH31
    Place 31-byte item on stack
    -
    3


    0x7f
    PUSH32
    Place 32-byte (full word) item on stack
    -
    3


    0x80
    DUP1
    Duplicate 1st stack item
    -
    3


    0x81
    DUP2
    Duplicate 2nd stack item
    -
    3


    0x82
    DUP3
    Duplicate 3rd stack item
    -
    3


    0x83
    DUP4
    Duplicate 4th stack item
    -
    3


    0x84
    DUP5
    Duplicate 5th stack item
    -
    3


    0x85
    DUP6
    Duplicate 6th stack item
    -
    3


    0x86
    DUP7
    Duplicate 7th stack item
    -
    3


    0x87
    DUP8
    Duplicate 8th stack item
    -
    3


    0x88
    DUP9
    Duplicate 9th stack item
    -
    3


    0x89
    DUP10
    Duplicate 10th stack item
    -
    3


    0x8a
    DUP11
    Duplicate 11th stack item
    -
    3


    0x8b
    DUP12
    Duplicate 12th stack item
    -
    3


    0x8c
    DUP13
    Duplicate 13th stack item
    -
    3


    0x8d
    DUP14
    Duplicate 14th stack item
    -
    3


    0x8e
    DUP15
    Duplicate 15th stack item
    -
    3


    0x8f
    DUP16
    Duplicate 16th stack item
    -
    3


    0x90
    SWAP1
    Exchange 1st and 2nd stack items
    -
    3


    0x91
    SWAP2
    Exchange 1st and 3rd stack items
    -
    3


    0x92
    SWAP3
    Exchange 1st and 4th stack items
    -
    3


    0x93
    SWAP4
    Exchange 1st and 5th stack items
    -
    3


    0x94
    SWAP5
    Exchange 1st and 6th stack items
    -
    3


    0x95
    SWAP6
    Exchange 1st and 7th stack items
    -
    3


    0x96
    SWAP7
    Exchange 1st and 8th stack items
    -
    3


    0x97
    SWAP8
    Exchange 1st and 9th stack items
    -
    3


    0x98
    SWAP9
    Exchange 1st and 10th stack items
    -
    3


    0x99
    SWAP10
    Exchange 1st and 11th stack items
    -
    3


    0x9a
    SWAP11
    Exchange 1st and 12th stack items
    -
    3


    0x9b
    SWAP12
    Exchange 1st and 13th stack items
    -
    3


    0x9c
    SWAP13
    Exchange 1st and 14th stack items
    -
    3


    0x9d
    SWAP14
    Exchange 1st and 15th stack items
    -
    3


    0x9e
    SWAP15
    Exchange 1st and 16th stack items
    -
    3


    0x9f
    SWAP16
    Exchange 1st and 17th stack items
    -
    3


    0xa0
    LOG0
    Append log record with no topics
    -
    375


    0xa1
    LOG1
    Append log record with one topic
    -
    750


    0xa2
    LOG2
    Append log record with two topics
    -
    1125


    0xa3
    LOG3
    Append log record with three topics
    -
    1500


    0xa4
    LOG4
    Append log record with four topics
    -
    1875


    0xa5 - 0xaf
    Unused
    -


    0xb0
    JUMPTO
    Tentative libevmasm has different numbers
    EIP 615


    0xb1
    JUMPIF
    Tentative
    EIP 615


    0xb2
    JUMPSUB
    Tentative
    EIP 615


    0xb4
    JUMPSUBV
    Tentative
    EIP 615


    0xb5
    BEGINSUB
    Tentative
    EIP 615


    0xb6
    BEGINDATA
    Tentative
    EIP 615


    0xb8
    RETURNSUB
    Tentative
    EIP 615


    0xb9
    PUTLOCAL
    Tentative
    EIP 615


    0xba
    GETLOCAL
    Tentative
    EIP 615


    0xbb - 0xe0
    Unused
    -


    0xe1
    SLOADBYTES
    Only referenced in pyethereum
    -
    -


    0xe2
    SSTOREBYTES
    Only referenced in pyethereum
    -
    -


    0xe3
    SSIZE
    Only referenced in pyethereum
    -
    -


    0xe4 - 0xef
    Unused
    -


    0xf0
    CREATE
    Create a new account with associated code
    -
    32000


    0xf1
    CALL
    Message-call into an account
    -
    Complicated


    0xf2
    CALLCODE
    Message-call into this account with alternative account’s code
    -
    Complicated


    0xf3
    RETURN
    Halt execution returning output data
    -
    0


    0xf4
    DELEGATECALL
    Message-call into this account with an alternative account’s code, but persisting into this account with an alternative account’s code
    -
    Complicated


    0xf5
    CREATE2
    Create a new account and set creation address to sha3(sender + sha3(init code)) % 2**160
    -


    0xf6 - 0xf9
    Unused
    -
    -


    0xfa
    STATICCALL
    Similar to CALL, but does not modify state
    -
    40


    0xfc
    TXEXECGAS
    Not in yellow paper FIXME
    -
    -


    0xfd
    REVERT
    Stop execution and revert state changes, without consuming all provided gas and providing a reason
    -
    0


    0xfe
    INVALID
    Designated invalid instruction
    -
    0


    0xff
    SELFDESTRUCT
    Halt execution and register account for later deletion
    -
    5000*



    Instruction DetailsADDTakes two words from stack, adds them, then pushes the result onto the stack.
    Pseudocode: push(s[0]+s[1])
    PUSHXThe following X bytes are read from PC, placed into a word, then this word is pushed onto the stack.
    CALL
    0 留言 2020-08-29 11:27:20 奖励30点积分
  • 从solc编译过程来理解solidity合约结构


    版权声明:本文由伏宸区块链安全实验室原创发布转载,请参考转载声明,注明出处: https://www.anquanke.com/post/id/164567

    最近在学习 solc 编译器方面的知识,看到这篇博文主要介绍得通俗易懂,故转载分享。
    现在以一个最简单的代码来开始我们的逆向旅程,为了方便学习,所有的代码编译和分析都在http://remix.ethereum.org/# 上进行.默认IDE 选项是关闭代码优化(Enable Optimization)和使用0.4.25 版本的solidity 编译器编译。
    pragma solidity ^0.4.24;contract test { function a() { uint a = 123; }}
    在Remix 上输入上述代码,点击Start to Compile 对代码进行编译,可以在Details 按钮里面获取编译出来的结果.结果包含如下:

    METADATA:编译器元数据,包含:编译器版本,编译器设置,源码信息等
    BYTECODE:合约编译完整的字节码结果
    ABI:应用程序接口,用于标识合约提供了哪些函数给外部调用
    WEB3DEPLOY:Web3js版合约部署代码
    METADATAHASH:元数据哈希
    GASESTIMATES:编译器计算函数调用需要消耗的Gas表
    RUNTIME BYTECODE:合约运行时字节码
    ASSEMBLY:字节码反汇编

    读者们会注意到,编译结果里面有 ByteCode 和 Runtime Bytecode, 分别表示什么意思呢?在此先略过这个疑问,我们关注Runtime Bytecode 中返回的字节码.对代码结构分析和字节码分析的标注后所有代码如下:
    000 PUSH1 80 002 PUSH1 40 004 MSTORE ; 把0x80 写到[0x40 ,0x40 + 0x20] 这块内存里面,因为内存是空的,这会创建新的内存 005 PUSH1 04 007 CALLDATASIZE ; 获取CALLDATA 的长度 008 LT ; LT 和PUSH1 0x4 对应,判断CALLDATA 的长度是否小于0x4 009 PUSH1 3f 011 JUMPI ; 如果小于0x4 就往下跳转到0x3F 012 PUSH1 00 014 CALLDATALOAD ; CALLDATALOAD 0x0 ,PUSH1 0x0 是给CALLDATALOAD 的参数,意思要获取CALLDATA 数据的偏移位置 015 PUSH29 0100000000000000000000000000000000000000000000000000000000 045 SWAP1 046 DIV ; DIV 和PUSH29 对应,意思是把上面的数据向左移28 字节,剩下4 字节是调用合约函数名的哈希 047 PUSH4 ffffffff 052 AND ; AND 和PUSH4 0xFFFFFFFF 对应,保留低位4 字节数据,高位去处 053 DUP1 054 PUSH4 0dbe671f ; 这个是合约有的函数名,经过sha3() 精简过的 059 EQ ; 判断传递过来的函数调用名是否相等 060 PUSH1 44 062 JUMPI ; 如果两值相等就往下跳转到0x44 063 JUMPDEST ; 空指令 064 PUSH1 00 066 DUP1 067 REVERT ; 没有匹配到相应的函数就撤销所有操作,Revert(0,0) 068 JUMPDEST 069 CALLVALUE ; 获取用户转帐数额 070 DUP1 071 ISZERO ; 如果用户转帐数额为0 072 PUSH1 4f 074 JUMPI ; 转帐数额不为0 则跳到0x4F,否则就退出 075 PUSH1 00 077 DUP1 078 REVERT ; 因为调用函数a() 是不需要附加转帐金额的,所以检测到带有附加金额的函数调用就退出,参考payable 关键字 079 JUMPDEST 080 POP 081 PUSH1 56 083 PUSH1 58 085 JUMP ; 跳转到地址88 086 JUMPDEST 087 STOP ; 停止执行 088 JUMPDEST 089 PUSH1 00 091 PUSH1 7b 093 SWAP1 094 POP 095 POP 096 JUMP ; 跳转到地址86 097 STOP ---- 合约代码结束分界线 ---- 098 LOG1 099 PUSH6 627a7a723058 106 SHA3 107 MUL 108 PUSH15 5fd8c2f6fe4103dba9baf9c48c052e 124 CALLDATALOAD 125 INVALID 126 PUSH1 d9 128 INVALID 129 INVALID 130 TIMESTAMP 131 STATICCALL 132 INVALID 133 INVALID 134 DUP13 135 INVALID 136 TIMESTAMP 137 INVALID 138 NUMBER 139 STOP 140 INVALID
    标注信息把合约代码的结构和执行过程的思路都理清了,但是读者们会发现以下的问题:

    为什么会有合约代码结束分界线,多出来的代码究竟是什么?
    为什么会有很多多余的跳转?
    JUMPDEST 是无意思的字节码,为什么会多次出现?

    要解决这些疑问,那么就需要深入到solidity 编译器的源码分析.在https://github.com/ethereum/solidity 中找到 solc 编译器的源码,定位到libsolidityCodegenContractCompiler.cpp 文件的ContractCompiler::compileContract() 函数,对该函数的分析如下:
    void ContractCompiler::compileContract( ContractDefinition const& _contract, std::map<const ContractDefinition*, eth::Assembly const*> const& _contracts) // 合约编译{ // ... initializeContext(_contract, _contracts); // 初始化执行环境上下文 appendFunctionSelector(_contract); // 根据合约内使用到的函数进行汇编构造 appendMissingFunctions(); // 链接不公开的函数(非public 声名)}
    initializeContext() 函数主要功能是初始化执行环境上下文,并把初始化的机器码输出到字节码缓存。
    void ContractCompiler::initializeContext( ContractDefinition const& _contract, map<ContractDefinition const*, eth::Assembly const*> const& _compiledContracts){ m_context.setExperimentalFeatures(_contract.sourceUnit().annotation().experimentalFeatures); m_context.setCompiledContracts(_compiledContracts); m_context.setInheritanceHierarchy(_contract.annotation().linearizedBaseContracts); CompilerUtils(m_context).initialiseFreeMemoryPointer(); // 初始化EVM 内存指针 registerStateVariables(_contract); m_context.resetVisitedNodes(&_contract);}const size_t CompilerUtils::freeMemoryPointer = 64;const size_t CompilerUtils::zeroPointer = CompilerUtils::freeMemoryPointer + 32;const size_t CompilerUtils::generalPurposeMemoryStart = CompilerUtils::zeroPointer + 32;void CompilerUtils::initialiseFreeMemoryPointer(){ m_context << u256(generalPurposeMemoryStart); // generalPurposeMemoryStart 的值为0x80,输出0x80 到字节码缓存 storeFreeMemoryPointer();}void CompilerUtils::storeFreeMemoryPointer(){ m_context << u256(freeMemoryPointer) << Instruction::MSTORE; // freeMemoryPointer 的值为0x40 ,输出0x40 和指令MSTORE 到字节码缓存}
    根据上面的代码可以知道,ContractCompiler::initializeContext() 会输出MSTORE 0x40,0x80 到合约字节码的头部,也就是我们常看到合约机器码的开头部分:6080604052 .appendFunctionSelector() 函数是把合约里面编译好的函数和合约初始化检测的代码组合在一起,如果没有深入了解appendFunctionSelector() 的代码生成过程,那就很难理解solc 为什么会这样生成字节码。
    void ContractCompiler::appendFunctionSelector(ContractDefinition const& _contract){ map<FixedHash<4>, FunctionTypePointer> interfaceFunctions = _contract.interfaceFunctions(); // 合约中声名的公开函数列表 map<FixedHash<4>, const eth::AssemblyItem> callDataUnpackerEntryPoints; // 函数代码入口点 if (_contract.isLibrary()) // 判断合约是否为库代码 { solAssert(m_context.stackHeight() == 1, "CALL / DELEGATECALL flag expected."); } FunctionDefinition const* fallback = _contract.fallbackFunction(); eth::AssemblyItem notFound = m_context.newTag(); // 创建新的汇编Tag ,Tag 的意义是用来标注汇编代码块声名和跳转到某一段汇编用的 // directly jump to fallback if the data is too short to contain a function selector // also guards against short data m_context << u256(4) << Instruction::CALLDATASIZE << Instruction::LT; // 判断CALLDATA 内容长度是否大于等于4 字节 m_context.appendConditionalJumpTo(notFound); // 插入条件跳转,LT 判断不通过就跳转到notFound 代码块 // retrieve the function signature hash from the calldata if (!interfaceFunctions.empty()) CompilerUtils(m_context).loadFromMemory(0, IntegerType(CompilerUtils::dataStartOffset * 8), true); // 从CALLDATA 中提取要调用的函数哈希 // 构造代码PUSH 0x00 ,CALLDATALOAD ,PUSH29 0100000000000000000000000000000000000000000000000000000000 ,SWAP1 ,DIV ,PUSH4 0xFFFFFFFF ,AND // stack now is: <can-call-non-view-functions>? <funhash> for (auto const& it: interfaceFunctions) { callDataUnpackerEntryPoints.insert(std::make_pair(it.first, m_context.newTag())); // 对函数入口创建新汇编代码块声名 m_context << dupInstruction(1) << u256(FixedHash<4>::Arith(it.first)) << Instruction::EQ; // 构造代码:DUP1 ,PUSH4 函数哈希 ,EQ m_context.appendConditionalJumpTo(callDataUnpackerEntryPoints.at(it.first)); // 如果数值相同,则跳转到目的函数地址,对应PUSH + JUMPI 指令 } m_context.appendJumpTo(notFound); // 没有找到的话就跳转到notFound 触发revert(0) 退出 m_context << notFound; // 声名notFound 的代码段 if (fallback) { solAssert(!_contract.isLibrary(), ""); if (!fallback->isPayable()) appendCallValueCheck(); solAssert(fallback->isFallback(), ""); solAssert(FunctionType(*fallback).parameterTypes().empty(), ""); solAssert(FunctionType(*fallback).returnParameterTypes().empty(), ""); fallback->accept(*this); m_context << Instruction::STOP; } else // TODO: error message here? m_context.appendRevert(); // 对notFound 的代码进行填充,因为fallback=fakse ,执行m_context.appendRevert() ,所以notFound 的代码序列是 PUSH1 0x00 ,DUP1 ,REVERT .意思是revert(0x0) // 上面是构造合约执行数据检测的代码,下面是对各个公开调用(指public 声名)的函数进行入口点构造 for (auto const& it: interfaceFunctions) { FunctionTypePointer const& functionType = it.second; solAssert(functionType->hasDeclaration(), ""); CompilerContext::LocationSetter locationSetter(m_context, functionType->declaration()); m_context << callDataUnpackerEntryPoints.at(it.first); if (_contract.isLibrary() && functionType->stateMutability() > StateMutability::View) // 库函数且关键字声名不是pure 和view 的函数 { // If the function is not a view function and is called without DELEGATECALL, // we revert. m_context << dupInstruction(2); m_context.appendConditionalRevert(); } m_context.setStackOffset(0); // We have to allow this for libraries, because value of the previous // call is still visible in the delegatecall. if (!functionType->isPayable() && !_contract.isLibrary()) // 如果函数没有启用Payable 关键字或者这是库函数的话,都不支持接收合约调用携带转帐金额 appendCallValueCheck(); // 添加对转帐金额检测代码 // Return tag is used to jump out of the function. eth::AssemblyItem returnTag = m_context.pushNewTag(); // 对函数创建返回代码段声名 if (!functionType->parameterTypes().empty()) // 如果函数有参数的话 { // Parameter for calldataUnpacker m_context << CompilerUtils::dataStartOffset; // CompilerUtils::dataStartOffset 指的是函数参数数据在TXDATA 里的偏移 m_context << Instruction::DUP1 << Instruction::CALLDATASIZE << Instruction::SUB; // 计算函数参数的大小 CompilerUtils(m_context).abiDecode(functionType->parameterTypes()); // 从TXDATA 中获取参数 } m_context.appendJumpTo(m_context.functionEntryLabel(functionType->declaration())); // 调转到函数入口点 m_context << returnTag; // 声名函数返回的代码段 // Return tag and input parameters get consumed. m_context.adjustStackOffset( CompilerUtils(m_context).sizeOnStack(functionType->returnParameterTypes()) - CompilerUtils(m_context).sizeOnStack(functionType->parameterTypes()) - 1 ); // Consumes the return parameters. appendReturnValuePacker(functionType->returnParameterTypes(), _contract.isLibrary()); // 构造函数返回值处理 }}
    上面的代码分析可能看起来有些晦涩难懂,作者把上面分析到的编译过程一一对应到编译结果并标注,汇编代码如下:
    ----- initializeContext() -> initialiseFreeMemoryPointer() ---- 000 PUSH1 80 ; initialiseFreeMemoryPointer() , m_context << u256(0x80) 002 PUSH1 40 ; storeFreeMemoryPointer() 004 MSTORE ; storeFreeMemoryPointer() , m_context << u256(0x40) << Instruction::MSTORE; ----- initialiseFreeMemoryPointer() ----- ----- appandFunctionSelector() Create Code Start --- 005 PUSH1 04 ; /-- 007 CALLDATASIZE ; | 008 LT ; | 检测CallData 是否合法,CallData 会带有4 字节函数哈希 009 PUSH1 3f ; | 011 JUMPI ; -- 012 PUSH1 00 ; /-- 014 CALLDATALOAD ; | 015 PUSH29 0100000000000000000000000000000000000000000000000000000000 045 SWAP1 ; | 046 DIV ; | 处理CallData 里面带入的函数哈希.默认读出来数据是在高位,现在处理成低位 047 PUSH4 ffffffff ; | 052 AND ; -- 053 DUP1 ; /-- 054 PUSH4 0dbe671f ; | 059 EQ ; | 060 PUSH1 44 ; | 根据函数哈希找入口 062 JUMPI ; | 063 JUMPDEST ; -- 064 PUSH1 00 ; /-- 066 DUP1 ; | notFound 代码填充 067 REVERT ; -- ----- appandFunctionSelector() 会给每个函数根据参数调用来分配函数头入口初始化检测代码 --- 068 JUMPDEST ; Address 0x44 , function a() Entry .. 069 CALLVALUE ; /-- 070 DUP1 ; | 071 ISZERO ; | 072 PUSH1 4f ; | 074 JUMPI ; | solc /libsolidity/Codegen/ContractCompiler.cpp:appendCallValueCheck() 075 PUSH1 00 ; | 077 DUP1 ; | 078 REVERT ; -- ----- Tag function_A_pre_JumpTo_function_A_Tag_Code ---- ----- m_context.appendJumpTo(m_context.functionEntryLabel(functionType->declaration())); 079 JUMPDEST ; JUMPDEST 是无意义的代码,它的唯一意义是用来标识这是一个Label 起始头 080 POP 081 PUSH1 56 ; eth::AssemblyItem returnTag = m_context.pushNewTag(); 0x56 is Return Address 083 PUSH1 58 ; / 085 JUMP ; m_context.appendJumpTo(m_context.functionEntryLabel(functionType->declaration())); ----- Tag function_A_return_Code ---- 086 JUMPDEST ; Address 0x56 087 STOP ; ContractCompiler::appendReturnValuePacker(); ----- Tag function_A_Main_Code ---- ----- CompilerContext 是保存每一个函数编译好的代码 088 JUMPDEST ; Address 0x58 , m_context.functionEntryLabel("a"); .. 089 PUSH1 00 091 PUSH1 7b 093 SWAP1 ; 0x7B ,0x00 == SWAP => 0x00 ,0x7B .意义是对栈进行平衡 094 POP 095 POP 096 JUMP ; Jump 0x56 097 STOP ; ----- appandFunctionSelector() Create Code End --- 098 LOG1 099 PUSH6 627a7a723058 106 SHA3 107 MUL 108 PUSH15 5fd8c2f6fe4103dba9baf9c48c052e 124 CALLDATALOAD 125 INVALID 126 PUSH1 d9 128 INVALID 129 INVALID 130 TIMESTAMP 131 STATICCALL 132 INVALID 133 INVALID 134 DUP13 135 INVALID 136 TIMESTAMP 137 INVALID 138 NUMBER 139 STOP 140 INVALID
    结合编译器的编译过程和编译出来的结果来阅读理解代码之后,可以知道合约汇编代码的结构:

    初始化EVM memory
    检测TXDATA 里面是否带有合法的函数哈希
    函数跳转
    函数预校验代码
    函数参数获取代码
    函数返回代码
    函数主体代码

    读者可能会有一个疑问,为什么在汇编代码 097 STOP 的后面还有多余的代码呢,这些代码的意义何在.我们来阅读CompilerStack::compileContract() 的代码:
    void CompilerStack::compileContract( ContractDefinition const& _contract, map<ContractDefinition const*, eth::Assembly const*>& _compiledContracts){ // ... shared_ptr<Compiler> compiler = make_shared<Compiler>(m_evmVersion, m_optimize, m_optimizeRuns); compiledContract.compiler = compiler; string metadata = createMetadata(compiledContract); // 创建元数据 compiledContract.metadata = metadata; bytes cborEncodedMetadata = createCBORMetadata( // 生成CBOR 元数据 metadata, !onlySafeExperimentalFeaturesActivated(_contract.sourceUnit().annotation().experimentalFeatures) ); try { // Run optimiser and compile the contract. compiler->compileContract(_contract, _compiledContracts, cborEncodedMetadata); // 编译合约 } catch(eth::OptimizerException const&) { solAssert(false, "Optimizer exception during compilation"); } // ...}
    可以看到,编译合约的时候 cborEncodedMetadata 的数据也带入 compileContract() ,compileContract() 代码如下:
    void Compiler::compileContract( ContractDefinition const& _contract, std::map<const ContractDefinition*, eth::Assembly const*> const& _contracts, bytes const& _metadata){ ContractCompiler runtimeCompiler(nullptr, m_runtimeContext, m_optimize); // 初始化合约编译类 runtimeCompiler.compileContract(_contract, _contracts); // 编译合约代码 m_runtimeContext.appendAuxiliaryData(_metadata); // 把CBOR 元数据附加在编译之后合约代码末端 // ...}
    那么回来阅读createCBORMetadata() 的代码,发现它其实是使用了元数据来构造出的数据。
    bytes CompilerStack::createCBORMetadata(string _metadata, bool _experimentalMode){ bytes cborEncodedHash = // CBOR-encoding of the key "bzzr0" bytes{0x65, 'b', 'z', 'z', 'r', '0'}+ // CBOR-encoding of the hash bytes{0x58, 0x20} + dev::swarmHash(_metadata).asBytes(); bytes cborEncodedMetadata; if (_experimentalMode) cborEncodedMetadata = // CBOR-encoding of {"bzzr0": dev::swarmHash(metadata), "experimental": true} bytes{0xa2} + cborEncodedHash + bytes{0x6c, 'e', 'x', 'p', 'e', 'r', 'i', 'm', 'e', 'n', 't', 'a', 'l', 0xf5}; else cborEncodedMetadata = // CBOR-encoding of {"bzzr0": dev::swarmHash(metadata)} bytes{0xa1} + cborEncodedHash; solAssert(cborEncodedMetadata.size() <= 0xffff, "Metadata too large"); // 16-bit big endian length cborEncodedMetadata += toCompactBigEndian(cborEncodedMetadata.size(), 2); return cborEncodedMetadata;}
    我们从Bytecode 中提取出CBOR 编码,数据为a165627a7a723058207ba6766efb653d5e4d3b7d5893d345b79718b5513bd5a87d5bf8256fa895c58d0029 ,对它的标注如下:
    a1 ; Flag : experimental = False 65627a7a72305820 ; CBOREncodeHash 7ba6766efb653d5e4d3b7d5893d345b79718b5513bd5a87d5bf8256fa895c58d ; BZZA hash 0029 ; hash 长度
    弄懂solidity 的编译过程和为什么会编译出这样的结果之后,现在回来解答前面提出的问题:

    为什么会有合约代码结束分界线,多出来的代码究竟是什么?

    多出来的代码是CBOR 元数据编码
    为什么会有很多多余的跳转?

    多余的跳转是因为appendFunctionSelector() 会帮助函数去构造预处理代码,参数提取代码和返回代码,最后才跳转到函数的主体代码.solidity 和x86 arm 等的汇编不同,它的对函数的参数和返回值处理都不是由函数主体来完成的。
    JUMPDEST 是无意思的字节码,为什么会多次出现?

    编译器在生成编译代码时,可以看到JUMP 和JUMPI 指令会跳转到JUMPDEST 指令.JUMPDEST 指令是solidity 编译器用来标识汇编代码的区段声名(Tag).所以后面的示例汇编代码都会在JUMPDEST 前记录代码区段的意思标注.

    至此,本文还有一个疑问没有被解决:ByteCode 和Runtime Bytecode 分别表示什么意思呢?我们来回顾Compiler::compileContract() 的完整代码:
    void Compiler::compileContract( ContractDefinition const& _contract, std::map<const ContractDefinition*, eth::Assembly const*> const& _contracts, bytes const& _metadata){ ContractCompiler runtimeCompiler(nullptr, m_runtimeContext, m_optimize); // 编译runtime 代码 runtimeCompiler.compileContract(_contract, _contracts); m_runtimeContext.appendAuxiliaryData(_metadata); // 插入CBOR 编码 // This might modify m_runtimeContext because it can access runtime functions at // creation time. ContractCompiler creationCompiler(&runtimeCompiler, m_context, m_optimize); // 编译creation 代码 m_runtimeSub = creationCompiler.compileConstructor(_contract, _contracts); m_context.optimise(m_optimize, m_optimizeRuns); // 优化汇编代码}
    可以看到 Compiler::compileContract() 里面分两部分来编译合约代码:runtime 的代码指的是合约编写逻辑的代码;creation 的代码指的是constructor() 的代码.我们回来看ByteCode 和RuntimeCode 的汇编代码来做对比。
    ByteCode 汇编:
    ---- Binary ---- 6080604052348015600f57600080fd5b50608d8061001e6000396000f300608060405260043610603f576000357c0100000000000000000000000000000000000000000000000000000000900463ffffffff1680630dbe671f146044575b600080fd5b348015604f57600080fd5b5060566058565b005b6000607b9050505600a165627a7a72305820026e5fd8c2f6fe4103dba9baf9c48c052e35ca60d9cdee42faca258c284224430029 ---- Constructor() Code ---- PUSH1 0x80 PUSH1 0x40 MSTORE CALLVALUE DUP1 ISZERO PUSH1 0xF JUMPI PUSH1 0x0 DUP1 REVERT JUMPDEST POP PUSH1 0x8D DUP1 PUSH2 0x1E PUSH1 0x0 CODECOPY PUSH1 0x0 RETURN STOP ---- Contract Code ---- PUSH1 0x80 PUSH1 0x40 MSTORE PUSH1 0x4 CALLDATASIZE LT PUSH1 0x3F JUMPI PUSH1 0x0 CALLDATALOAD PUSH29 0x100000000000000000000000000000000000000000000000000000000 SWAP1 DIV PUSH4 0xFFFFFFFF AND DUP1 PUSH4 0xDBE671F EQ PUSH1 0x44 JUMPI JUMPDEST PUSH1 0x0 DUP1 REVERT JUMPDEST CALLVALUE DUP1 ISZERO PUSH1 0x4F JUMPI PUSH1 0x0 DUP1 REVERT JUMPDEST POP PUSH1 0x56 PUSH1 0x58 JUMP JUMPDEST STOP JUMPDEST PUSH1 0x0 PUSH1 0x7B SWAP1 POP POP JUMP STOP
    RuntimeCode 汇编:
    ---- Binary ---- 608060405260043610603f576000357c0100000000000000000000000000000000000000000000000000000000900463ffffffff1680630dbe671f146044575b600080fd5b348015604f57600080fd5b5060566058565b005b6000607b9050505600a165627a7a72305820026e5fd8c2f6fe4103dba9baf9c48c052e35ca60d9cdee42faca258c284224430029 ---- Contract Code ---- PUSH1 0x80 PUSH1 0x40 MSTORE PUSH1 0x4 CALLDATASIZE LT PUSH1 0x3F JUMPI PUSH1 0x0 CALLDATALOAD PUSH29 0x100000000000000000000000000000000000000000000000000000000 SWAP1 DIV PUSH4 0xFFFFFFFF AND DUP1 PUSH4 0xDBE671F EQ PUSH1 0x44 JUMPI JUMPDEST PUSH1 0x0 DUP1 REVERT JUMPDEST CALLVALUE DUP1 ISZERO PUSH1 0x4F JUMPI PUSH1 0x0 DUP1 REVERT JUMPDEST POP PUSH1 0x56 PUSH1 0x58 JUMP JUMPDEST STOP JUMPDEST PUSH1 0x0 PUSH1 0x7B SWAP1 POP POP JUMP STOP
    所以,我们可以明白在部署合约的时候,EVM 执行Constructor() 函数的代码初始化合约数据,后续用户通过Web3 调用节点上的合约函数时,是直接在RuntimeCode 中开始执行合约代码.TXDATA 中是带有用户希望调用函数的哈希和函数的参数数据的,接下来合约代码初始EVM Memory 之后,根据TXDATA 里面指向用户希望调用的函数哈希来进行代码跳转.执行函数主体代码前做一些预检测并从TXDATA 中提取函数参数到栈,最后执行函数主体代码并退出。
    0 留言 2020-08-17 18:50:16 奖励30点积分
  • Solidity字节码Bytecode的理解


    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明原文链接:https://blog.csdn.net/Programmer_CJC/article/details/80217672https://blog.csdn.net/Programmer_CJC/article/details/80218649https://blog.csdn.net/Programmer_CJC/article/details/80219720

    最近在学习solidity方面的知识,看到这几篇博文主要介绍evm bytecode的,通俗易懂,故转载分享。
    一、从Bytecode角度分析,EVM如何在基本块之间跳转1.1 BasicBlock1.1.1 条件跳转(JUMPI)1.1.2 非条件跳转(JUMP)1.1.3 Fall to二、EVM Bytecode文件结构以及如何执行三、用solc编译smart contract,用evm反编译bytecode一、从Bytecode角度分析,EVM如何在基本块之间跳转1.1 BasicBlock在解释EVM是如何执行之前,先来解释一下BasicBlock(基本块)。一个基本块由一系列的指令构成,有一个入口和一个出口,入口就是第一个指令,出口就是最后一个指令。
    出口的类型有:

    条件跳转(JUMPI)
    非条件跳转(JUMP)
    结束指令(RETURN,REVERT)
    什么都没有,直接fall to下一个block

    1.1.1 条件跳转(JUMPI)EVM中条件跳转的指令是JUMPI,它会从stack中读取2个元素,分别代表跳转的条件和pc(programmer counter)。下面是一个JUMPI的跳转例子:

    Block1: JUMPDEST CALLVALUE ISZERO PUSH2 0x0100 JUMPI
    Block2: PUSH1 0x00 DUP1 REVERT

    Block1由5个指令构成(PUSH2 0x0100是一个), JUMPDEST表明这个Block是一个跳转的起始位置,CALLVALUE代表从transaction中获得的值,比如用户发送的ether额度,就可以用该指令获得。ISZERO判断CALLVALUE获得的值是否为0, PUSH指令向stack中放入了一个值。最后执行到JUMPI,它从条件中读取了两个值:

    ISZERO(CALLVALUE)
    0x0100

    如果满足1,则跳转到0x0100指向的block, 否则继续执行下一个BasicBlock(Block2) (PS: 如果满足条件跳转之后,执行完跳转的Block会继续往下执行Block2,执行的方式是深度优先遍历的方式)。
    1.1.2 非条件跳转(JUMP)EVM中的非条件跳转由JUMP指令触发, 每次执行到JUMP指令时,都会从stack读出1个值,表示要跳转的pc。和JUMPI指令类似,执行完跳转块后,也会继续向下执行,执行方式是深度优先遍历。
    1.1.3 Fall toEVM的某些基本块没有跳转指令也没有结束指令,对于这些指令,执行完最后一个指令后会继续执行下一个指令。当然对于条件跳转来说,也会有fall to的情况。如在条件跳转中举的例子,在执行完Block1之后,会继续执行Block2。或者Block1的JUMPI跳转条件不满足,也会继续执行Block2。
    二、EVM Bytecode文件结构以及如何执行该小节用一个具体的smart contract以及对应的指令来具体解释EVM bytecode的文件结构以及bytecode如何执行。
    pragma solidity ^0.4.22;contract Demo{ uint public value1 = 0; uint public value2 = 0; function A(uint v) public returns(uint){ value1 += v; return value1; } function B(uint v) public{ value2 += A(v); }}
    上面的智能合约来做例子,由于Bytecode过长就不上传,可以将该代码贴到 http://remix.ethereum.org/#optimize=false&version=soljson-v0.4.22+commit.4cb486ee.js ,直接点击右侧的Details来查看Bytecode:

    下面开始解释一下Bytecode的结构:

    从上面的图来看,Bytecode由两部分构成。第一部分的.code包含了一些smart contract初始化的代码,比如构造函数,state variable(全局变量)的赋值等操作。区块链上,这些都是EOA在部署合约时就执行完成的,在区块链浏览器,如Etherscan,都是无法看到这部分的代码的(某些开源合约会公开这部分的信息,默认是没有的)。
    从.data开始,是smart contract的runtime bytecode,也就是在区块链上保存的合约的bytecode。想要获得该部分的bytecode,可以安装solidity( https://github.com/ethereum/solidity ),通过命令 solc —bin-runtime filePath获得。
    Remix的结构有点不太一样,是由若干个tag组成的,每个tag由若干个基本块组成。以JUMPDEST或者结束指令(RETURN,REVERT,STOP)划分。.code部分是Bytecode的入口,这部分的指令包含了所有能够被外部调用的函数的函数签名和跳转pc(programmer counter)值。

    上面的5个框分别是该合约的5个跳转函数。可能会奇怪合约就2个函数,为何会有5个可跳转函数。这5个跳转函数分别是:1. fallback(回退函数),2个public全局变量,2个public函数。
    首先解释一下回退函数,在EVM中,回退函数是唯一一个未命名的函数,可以发现其他4个框前面都有一个函数签名,如第二个框的3033413B,只有fallback function没有。因此如果我们调用了一个合约中没有的函数,没有一个函数签名能满足,接下来的四个框都不会满足跳转条件,因此会通过fall to的形式执行tag 1,tag 1也就是fallback函数的开始位置。
    接下来说一下什么是函数签名。函数签名是一个4byte的hash值,用来唯一标识smart contract中的函数。它是通过sha3(“functionName(type1, type2)”),取前4bytes得到的。也就是说该函数签名只与函数名,函数类型有关。
    总结一下.code部分,该部分包含了合约能调用的所有函数的跳转地址,从上图中体现就是tag1-5. tag 1-5分别是5个函数的起始位置。

    下面用函数B为例,解释一下EVM的bytecode是如何跳转的:

    要调用函数B,首先EVM会接受到函数签名(DAC0EB07),在.code部分中,跳转到tag 5
    tag 5是函数B的开始部分,tag 5中有一个JUMPI,假设跳转条件满足,EVM会跳转到tag 15,如果不满足条件,则会执行PUSH, DUP1, REVERT. REVERT是终止指令,程序终于。该部分通常是用来判断一个函数是否是payable的。比如CALLVALUE指令会得到transacation是否发了Ether,如果发了ether,ISZERO的结果就会是false,因此不会执行跳转
    执行tag 15, 执行到最后有一个JUMP指令,会从EVM stack读出一个值, 上一个push到stack的值是tag 17,因此跳转到tag 17
    执行tag 17,同tag 15,tag17最后的tag 15会使pc跳转到tag14(tag 14也就是函数A的函数体部分)
    执行tag 14,执行到最后有一个JUMP指令,这时JUMP指令读到的是tag 17中push的tag 20
    执行tag 20, tag20最后的JUMP指令,执行的是tag15中的push tag 16, 因此会跳转到tag 16
    执行tag 16,执行到stop指令,程序终止


    以函数A为例:

    要调用函数A,首先EVM会接收到函数签名(A17A9E66),在.code部分中,跳转到tag 4
    tag 4是函数A的开始部分,假设满足JUMPI的跳转条件,则跳转到tag 12,如果不满足,则继续执行下面的三个指令
    tag 12代表函数读取参数的过程,函数B没有参数因此没有这一部分。最后由JUMP指令跳转到tag 14
    执行tag 14,最后的JUMP读取到的是tag 12中的PUSH tag 13
    执行tag 13, tag 13最后的终止指令是RETURN,代表函数执行结束并返回值

    三、用solc编译smart contract,用evm反编译bytecode首先需要安装solc和evm:

    solc: https://github.com/ethereum/solidity/releases
    evm: https://geth.ethereum.org/downloads

    编译一个smart contract可以通过指令来得到bytecode:
    solc --bin-runtime filepath反编译bytecode可以通过:
    evm --dissam bytecodeFilePath反编译以后的文件如下:

    前面的数字就是pc(programmer counter), 以20行的指令为例,0x008d代表21行的JUMPI跳转的pc值是141.
    solc还有下面几个非常好用的指令,可以获得合约的ast,asm(汇编码),opcode,bin,abi,函数签名等:
    0 留言 2020-08-14 14:53:07 奖励30点积分
  • 记c# u3d 之前犯得一点错误


    声明一个数组后,忘记new一个具体大小,导致无法传递值报错
    忘记Array.sort() 可以排序数字,甚至闭门造了个轮子,服了(而且人家还先进一点,我这个简直是shit)
    float[] sortBySpeed(float[] array){ float temp = 0; float[] sortArray=new float[array.Length]; for (int i = 0; i < array.Length; i++) { sortArray[i] = i; } //声明并创造一个序号数组,并在后面的排序中,与速度保持一样的变化; for (int i = 0; i < array.Length; i++) { for (int j = i+1; j < array.Length; j++) { if (array[j]>array[i]) { temp = array[i]; array [i] = array [j]; array [j] = temp; temp = sortArray[i]; sortArray[i] = sortArray[j]; sortArray[j] = temp; } } } return sortArray;}用inistaniate克隆物体,并获取transform.positon,在自动布局组(gridout),如果不延时的话,立即获取会直接获取出生点的坐标导致误差
    预制体的位置不对还可能是没有设置rect的轴心和位置
    如果意外情况(代码挂载脚本),如果开头声明了一个bool值为false的变量,有可能会声明两次变为true(???俺也不知道为什么)
    单例模式的代码尽量简洁一点吧,突然忘了加声明可能会很心伤、
    可以用out,ref声明来在方法中传值和引用(该死,以前学了忘了),不过用多了,代码修改很麻烦,慎重、
    可能要学学画思维导图,设计代码结构有点不合理(三个类打天下,绝了)
    0 留言 2020-08-06 14:25:52 奖励20点积分
  • 进程挂起再恢复实现进程内存替换

    背景所谓的进程内存替换,就是指将一个进程的内存数据清空,写入任意我们想写入的数据,并更改执行顺序,执行我们写入的数据代码。
    本文介绍的就是这样的编程技术,但是,我们做了一些简化,简化成实现创建一个挂起主线程的进程,在新进程的地址空间内申请一块内存,写入我们的 Shellcode,并更改新进程执行顺序,执行我们的 Shellcode 代码。现在,我就把实现过程和原理整理成文档,分享给大家。
    函数介绍GetThreadContext 函数
    获取指定线程的上下文。64 位应用程序可以使用 Wow64GetThreadContext 函数来检索 WOW64 线程的上下文。
    函数声明
    BOOL WINAPI GetThreadContext( _In_ HANDLE hThread, _Inout_ LPCONTEXT lpContext);
    参数

    hThread [in]要检索其上下文的线程的句柄。 该句柄必须具有对线程的THREAD_GET_CONTEXT访问权限。 有关更多信息,请参阅线程安全和访问权限。WOW64:手柄也必须有THREAD_QUERY_INFORMATION访问权限。lpContext [in,out]指向 CONTEXT 结构的指针,它接收指定线程的适当上下文。 该结构的ContextFlags成员的值指定检索线程的上下文的哪些部分。 CONTEXT结构具有高度的处理器特性。 请参阅WinNT.h头文件,了解该结构的处理器特定定义和任何对齐要求。
    返回值

    如果函数成功,则返回值不为零。如果函数失败,返回值为零。 要获取扩展错误信息,请调用GetLastError。

    SetThreadContext 函数
    设置指定线程的上下文。64 位应用程序可以使用 Wow64SetThreadContext 函数设置 WOW64 线程的上下文。
    函数声明
    BOOL WINAPI SetThreadContext( _In_ HANDLE hThread, _In_ const CONTEXT *lpContext);
    参数

    hThread [in]线程的句柄,其上下文将被设置。 该句柄必须具有线程的THREAD_SET_CONTEXT权限。 有关更多信息,请参阅线程安全和访问权限。lpContext [in]指向包含要在指定线程中设置的上下文的CONTEXT结构的指针。 此结构的ContextFlags成员的值指定要设置的线程的上下文的哪些部分。 无法指定的CONTEXT结构中的某些值将默认设置为正确的值。 这包括指定特权处理器模式的CPU状态寄存器中的位,调试寄存器中的全局使能位以及必须由操作系统控制的其他状态。
    返回值

    如果设置了上下文,则返回值为非零。如果函数失败,返回值为零。 要获取扩展错误信息,请调用GetLastError。

    ResumeThread 函数
    减少线程的暂停计数。 当暂停计数递减到零时,线程的执行被恢复。
    函数声明
    DWORD WINAPI ResumeThread( _In_ HANDLE hThread);
    参数

    hThread [in]
    要重新启动的线程的句柄。
    该句柄必须具有THREAD_SUSPEND_RESUME权限。 有关更多信息,请参阅线程安全和访问权限。

    返回值

    如果函数成功,则返回值是线程先前的挂起计数。如果函数失败,返回值为(DWORD)-1。 要获取扩展错误信息,请调用GetLastError。

    实现原理我们实现进程内存替换,或者说实现进程数据写入,更改执行顺序的原理是:

    首先,使用 CreateProcess 函数创建进程,并且设置创建进程的标志为 CREATE_SUSPENDED,即表示新进程的主线程被挂起。
    然后,使用 VirtualAllocEx 函数在新进程中申请一块可读、可写、可执行的内存,并使用 WriteProcessMemory 函数写入Shellcode 数据。
    接着,使用 GetThreadContext,设置获取标志为 CONTEXT_FULL,即获取新进程中所有的线程上下文。并修改线程上下文的指令指针 EIP 的值,更改主线程的执行顺序。再将修改过的线程上下文设置回主线程中。
    最后,我们调用 ResumeThread 恢复主线程,让进程按照修改后的 EIP 继续运行,执行我们的 Shellcode 代码。

    其中,当使用 CreateProcess 创建进程时,创建标志为 CREATE_SUSPENDED,则表示新进程的主线程被创建为挂起状态,直到使用 ResumeThread 函数恢复主线程,进程才会继续运行。
    其中,要注意的是,在使用 GetThreadContext 获取线程上下文的时候,一定要对 CONTEXT 机构中的 ContextFlags 成员赋值,表示指明要检索线程的上下文的哪些部分,否则会导致程序实现不到想要的效果。我们可以指明 CONTEXT_FULL,表示获取所有的线程上下文信息。
    编码实现// 创建进程并替换进程内存数据, 更改执行顺序BOOL ReplaceProcess(char *pszFilePath, PVOID pReplaceData, DWORD dwReplaceDataSize, DWORD dwRunOffset){ STARTUPINFO si = { 0 }; PROCESS_INFORMATION pi = { 0 }; CONTEXT threadContext = { 0 }; BOOL bRet = FALSE; ::RtlZeroMemory(&si, sizeof(si)); ::RtlZeroMemory(&pi, sizeof(pi)); ::RtlZeroMemory(&threadContext, sizeof(threadContext)); si.cb = sizeof(si); // 创建进程并挂起主线程 bRet = ::CreateProcess(pszFilePath, NULL, NULL, NULL, FALSE, CREATE_SUSPENDED, NULL, NULL, &si, &pi); if (FALSE == bRet) { ShowError("CreateProcess"); return FALSE; } // 在替换的进程中申请一块内存 LPVOID lpDestBaseAddr = ::VirtualAllocEx(pi.hProcess, NULL, dwReplaceDataSize, MEM_COMMIT | MEM_RESERVE, PAGE_EXECUTE_READWRITE); if (NULL == lpDestBaseAddr) { ShowError("VirtualAllocEx"); return FALSE; } // 写入替换的数据 bRet = ::WriteProcessMemory(pi.hProcess, lpDestBaseAddr, pReplaceData, dwReplaceDataSize, NULL); if (FALSE == bRet) { ShowError("WriteProcessError"); return FALSE; } // 获取线程上下文 // 注意此处标志,一定要写!!! threadContext.ContextFlags = CONTEXT_FULL; bRet = ::GetThreadContext(pi.hThread, &threadContext); if (FALSE == bRet) { ShowError("GetThreadContext"); return FALSE; } // 修改进程的PE文件的入口地址以及映像大小,先获取原来进程PE结构的加载基址 threadContext.Eip = (DWORD)lpDestBaseAddr + dwRunOffset; // 设置挂起进程的线程上下文 bRet = ::SetThreadContext(pi.hThread, &threadContext); if (FALSE == bRet) { ShowError("SetThreadContext"); return FALSE; } // 恢复挂起的进程的线程 ::ResumeThread(pi.hThread); return TRUE;}
    程序测试我们运行程序,对 520.exe 程序创建挂起进程,并写入 Shellcode,更改进程执行顺序,恢复进程,执行 Shellcode 部分代码:

    总结这个程序在理解原理后,你会发现我们上述的例子并没有替换原来新进程的内存,只是申请了一块新内存,并写入 Shellcode 数据。但是,要替换新进程的内存倒也不难,只要获取了新进程的加载基址,然后根据 PE 格式,获取加载映像大小,并对数据全部置零清空,在写入我们的新数据,这样就实现了替换。但是,只要你理解了本文演示的例子,实现替换操作也不难了。
    如果你仍然不明白,可以多看看 CreateProcess、GetThreadContext、SetThreadContext、ResumeThread 等函数的具体参数说明,理解清楚参数含义就可以了。
    其中,要注意的是,在使用 GetThreadContext 获取线程上下文的时候,一定要对 CONTEXT 机构中的 ContextFlags 成员赋值,表示指明要检索线程的上下文的哪些部分,否则会导致程序实现不到想要的效果。我们可以指明 CONTEXT_FULL,表示获取所有的线程上下文信息。
    参考参考自《Windows黑客编程技术详解》一书
    4 留言 2019-01-22 17:34:57 奖励15点积分
  • 查找并使用PspTerminateThreadByPointer函数强制结束进程可以杀360进程 精华

    背景学习计算机的同学,或多或少都会有一个黑客情节。总是会想成为一个无拘无束的“黑客”,探索计算机世界里技术的边缘,挑战一切规则与界限。其实,正如电影《东邪西毒》里欧阳峰说的:“人都会经历这个阶段,看见一座山,就想知道山后面是什么。我很想告诉ta,可能翻过去山后面,你会发觉没有什么特别,回头看会觉得这边更好”。
    本文要介绍的就是在内核下实现,强制关掉指定进程,甚至可以关闭 360、QQ 等进程。这个技术,虽不能让你成为一名“黑客”,或许可以让你感受一把“黑科技”的瘾。现在,我就把实现过程和原理整理成文档,分享给大家。该程序适用于 32 位和 64 位 Win7 到 Win10 全平台系统。
    实现过程我们知道,线程是进程中执行运算的最小单位,是进程中的一个实体,是被系统独立调度和分派的基本单位,线程自己不拥有系统资源,只拥有一点在运行中必不可少的资源,但它可与同属一个进程的其它线程共享进程所拥有的全部资源。一个线程可以创建和撤消另一个线程,同一进程中的多个线程之间可以并发执行。
    也就是说,当一个进程中的所有线程都被结束的时候,这个进程也就没有了存在的意义,也随之结束了。这,便是我们本文介绍的这种强制杀进程的实现原理,即把进程中的线程都杀掉,从而让进程消亡,实现间接杀进程的效果。
    Windows 提供了一个导出的内核函数 PsTerminateSystemThread 来帮助我们结束线程,所以,类似 360、QQ 等也会对重点监测该函数,防止结束自己的线程。我们通过逆向 PsTerminateSystemThread 函数,可以发现该函数实际上调用了未导出的内核函数 PspTerminateThreadByPointer 来实现的结束线程的操作。所以,我们可以通过查找 PspTerminateThreadByPointer 函数地址,调用直接它来结束线程,就可以绕过绝大部分的进程保护,实现强制杀进程。
    PspTerminateThreadByPointer 的函数声明为:
    NTSTATUS PspTerminateThreadByPointer ( PETHREAD pEThread, NTSTATUS ntExitCode, BOOLEAN bDirectTerminate );
    但要注意,PspTerminateThreadByPointer 的函数指针的声明的调用约定:
    // 32 位typedef NTSTATUS(*PSPTERMINATETHREADBYPOINTER_X86) ( PETHREAD pEThread, NTSTATUS ntExitCode, BOOLEAN bDirectTerminate );// 64 位typedef NTSTATUS(__fastcall *PSPTERMINATETHREADBYPOINTER_X64) ( PETHREAD pEThread, NTSTATUS ntExitCode, BOOLEAN bDirectTerminate );
    其中,PsTerminateSystemThread 里会调用 PspTerminateThreadByPointer 函数。我们使用 WinDbg 逆向 Win8.1 x64 里的 PsTerminateSystemThread 函数,如下所示:
    nt!PsTerminateSystemThread:fffff800`83904518 8bd1 mov edx,ecxfffff800`8390451a 65488b0c2588010000 mov rcx,qword ptr gs:[188h]fffff800`83904523 f7417400080000 test dword ptr [rcx+74h],800hfffff800`8390452a 7408 je nt!PsTerminateSystemThread+0x1c (fffff800`83904534)fffff800`8390452c 41b001 mov r8b,1fffff800`8390452f e978d9fcff jmp nt!PspTerminateThreadByPointer (fffff800`838d1eac)fffff800`83904534 b80d0000c0 mov eax,0C000000Dhfffff800`83904539 c3 ret
    由上面代码可以知道,我们可以通过扫描 PsTerminateSystemThread 内核函数中的特征码,从而获取 PspTerminateThreadByPointer 函数的偏移,再根据偏移计算出该函数的地址。其中,不同系统中的特征码也会不同,下面是我使用 WinDbg 逆向各个系统上总结的特征码的情况:




    Win 7
    win 8.1
    win 10




    32 位
    0xE8
    0xE8
    0xE8


    64 位
    0xE8
    0xE9
    0xE9



    那么,我们强制杀进程的实现原理为:

    首先,根据特征码扫描内存,获取 PspTerminateThreadByPointer 函数地址
    然后,调用 PsLookupProcessByProcessId 函数,根据将要结束进程 ID 获取对应的进程结构对象 EPROCESS
    接着,遍历所有的线程 ID,并调用 PsLookupThreadByThreadId 函数根据线程 ID 获取对应的线程结构 ETHREAD
    然后,调用函数 PsGetThreadProcess 获取线程结构 ETHREAD 对应的进程结构 EPROCESS
    这时,我们可以通过判断该进程是不是我们指定要结束的进程,若是,则调用 PspTerminateThreadByPointer 函数结束线程;否则,继续遍历下一个线程 ID
    重复上述 3、4、5 的操作,直到线程遍历完毕

    这样,我们就可以查杀指定进程的所有线程,线程被结束之后,进程也随之结束。注意的是,当调用 PsLookupProcessByProcessId 和 PsLookupThreadByThreadId 等 LookupXXX 系列函数获取对象的时候,都需要调用 ObDereferenceObject 函数释放对象,否则在某些时候会造成蓝屏。
    编码实现强制结束指定进程// 强制结束指定进程NTSTATUS ForceKillProcess(HANDLE hProcessId){ PVOID pPspTerminateThreadByPointerAddress = NULL; PEPROCESS pEProcess = NULL; PETHREAD pEThread = NULL; PEPROCESS pThreadEProcess = NULL; NTSTATUS status = STATUS_SUCCESS; ULONG i = 0;#ifdef _WIN64 // 64 位 typedef NTSTATUS(__fastcall *PSPTERMINATETHREADBYPOINTER) (PETHREAD pEThread, NTSTATUS ntExitCode, BOOLEAN bDirectTerminate);#else // 32 位 typedef NTSTATUS(*PSPTERMINATETHREADBYPOINTER) (PETHREAD pEThread, NTSTATUS ntExitCode, BOOLEAN bDirectTerminate);#endif // 获取 PspTerminateThreadByPointer 函数地址 pPspTerminateThreadByPointerAddress = GetPspLoadImageNotifyRoutine(); if (NULL == pPspTerminateThreadByPointerAddress) { ShowError("GetPspLoadImageNotifyRoutine", 0); return FALSE; } // 获取结束进程的进程结构对象EPROCESS status = PsLookupProcessByProcessId(hProcessId, &pEProcess); if (!NT_SUCCESS(status)) { ShowError("PsLookupProcessByProcessId", status); return status; } // 遍历所有线程, 并结束所有指定进程的线程 for (i = 4; i < 0x80000; i = i + 4) { status = PsLookupThreadByThreadId((HANDLE)i, &pEThread); if (NT_SUCCESS(status)) { // 获取线程对应的进程结构对象 pThreadEProcess = PsGetThreadProcess(pEThread); // 结束指定进程的线程 if (pEProcess == pThreadEProcess) { ((PSPTERMINATETHREADBYPOINTER)pPspTerminateThreadByPointerAddress)(pEThread, 0, 1); DbgPrint("PspTerminateThreadByPointer Thread:%d\n", i); } // 凡是Lookup...,必需Dereference,否则在某些时候会造成蓝屏 ObDereferenceObject(pEThread); } } // 凡是Lookup...,必需Dereference,否则在某些时候会造成蓝屏 ObDereferenceObject(pEProcess); return status;}
    获取 PspTerminateThreadByPointer 函数地址// 获取 PspTerminateThreadByPointer 函数地址PVOID GetPspLoadImageNotifyRoutine(){ PVOID pPspTerminateThreadByPointerAddress = NULL; RTL_OSVERSIONINFOW osInfo = { 0 }; UCHAR pSpecialData[50] = { 0 }; ULONG ulSpecialDataSize = 0; // 获取系统版本信息, 判断系统版本 RtlGetVersion(&osInfo); if (6 == osInfo.dwMajorVersion) { if (1 == osInfo.dwMinorVersion) { // Win7#ifdef _WIN64 // 64 位 // E8 pSpecialData[0] = 0xE8; ulSpecialDataSize = 1;#else // 32 位 // E8 pSpecialData[0] = 0xE8; ulSpecialDataSize = 1;#endif } else if (2 == osInfo.dwMinorVersion) { // Win8#ifdef _WIN64 // 64 位#else // 32 位#endif } else if (3 == osInfo.dwMinorVersion) { // Win8.1#ifdef _WIN64 // 64 位 // E9 pSpecialData[0] = 0xE9; ulSpecialDataSize = 1;#else // 32 位 // E8 pSpecialData[0] = 0xE8; ulSpecialDataSize = 1;#endif } } else if (10 == osInfo.dwMajorVersion) { // Win10#ifdef _WIN64 // 64 位 // E9 pSpecialData[0] = 0xE9; ulSpecialDataSize = 1;#else // 32 位 // E8 pSpecialData[0] = 0xE8; ulSpecialDataSize = 1;#endif } // 根据特征码获取地址 pPspTerminateThreadByPointerAddress = SearchPspTerminateThreadByPointer(pSpecialData, ulSpecialDataSize); return pPspTerminateThreadByPointerAddress;}
    根据特征码获取 PspTerminateThreadByPointer 数组地址// 根据特征码获取 PspTerminateThreadByPointer 数组地址PVOID SearchPspTerminateThreadByPointer(PUCHAR pSpecialData, ULONG ulSpecialDataSize){ UNICODE_STRING ustrFuncName; PVOID pAddress = NULL; LONG lOffset = 0; PVOID pPsTerminateSystemThread = NULL; PVOID pPspTerminateThreadByPointer = NULL; // 先获取 PsTerminateSystemThread 函数地址 RtlInitUnicodeString(&ustrFuncName, L"PsTerminateSystemThread"); pPsTerminateSystemThread = MmGetSystemRoutineAddress(&ustrFuncName); if (NULL == pPsTerminateSystemThread) { ShowError("MmGetSystemRoutineAddress", 0); return pPspTerminateThreadByPointer; } // 然后, 查找 PspTerminateThreadByPointer 函数地址 pAddress = SearchMemory(pPsTerminateSystemThread, (PVOID)((PUCHAR)pPsTerminateSystemThread + 0xFF), pSpecialData, ulSpecialDataSize); if (NULL == pAddress) { ShowError("SearchMemory", 0); return pPspTerminateThreadByPointer; } // 先获取偏移, 再计算地址 lOffset = *(PLONG)pAddress; pPspTerminateThreadByPointer = (PVOID)((PUCHAR)pAddress + sizeof(LONG) + lOffset); return pPspTerminateThreadByPointer;}
    指定内存区域的特征码扫描// 指定内存区域的特征码扫描PVOID SearchMemory(PVOID pStartAddress, PVOID pEndAddress, PUCHAR pMemoryData, ULONG ulMemoryDataSize){ PVOID pAddress = NULL; PUCHAR i = NULL; ULONG m = 0; // 扫描内存 for (i = (PUCHAR)pStartAddress; i < (PUCHAR)pEndAddress; i++) { // 判断特征码 for (m = 0; m < ulMemoryDataSize; m++) { if (*(PUCHAR)(i + m) != pMemoryData[m]) { break; } } // 判断是否找到符合特征码的地址 if (m >= ulMemoryDataSize) { // 找到特征码位置, 获取紧接着特征码的下一地址 pAddress = (PVOID)(i + ulMemoryDataSize); break; } } return pAddress;}
    程序测试在 Win7 32 位系统下,驱动程序正常执行:

    在 Win8.1 32 位系统下,驱动程序正常执行:

    在 Win10 32 位系统下,驱动程序正常执行:

    在 Win7 64 位系统下,驱动程序正常执行:

    在 Win8.1 64 位系统下,驱动程序正常执行:

    在 Win10 64 位系统下,驱动程序正常执行:

    总结这个程序的原理不难理解,关键是如何定位 PspTerminateThreadByPointer 未导出的内核函数在 PsTerminateSystemThread 函数中的位置,要在各个版本系统上进行逆向,以确定内存特征码。
    参考参考自《Windows黑客编程技术详解》一书
    3 留言 2019-02-23 21:08:48 奖励26点积分
  • 基于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》清华大学出版社(台湾)良格葛编写。
    3 留言 2020-06-23 12:40:13 奖励66点积分
  • weka数据分类小实验

    一、实验目的
    熟悉weka基本功能和使用方法
    学习对数据集进行分类训练并测试
    比较不同分类算法对本实验测试集预测的准确率

    二、实验环境
    平台:Weka3.8
    数据集:将Weka的data文件夹下默认数据集vote.arff的前20个实例作为测试集,其余实例作为训练集

    三、实验概况
    观察数据集的属性类别以及实例来确定是否进行过滤处理
    利用训练集分别采用C4.5决策树分类器、基于规则的分类器和K最近邻三种算法进行分类训练,并对测试集进行预测
    比较三种分类器对本实验数据集分类模型的优劣

    四、实验内容4.1 观察数据集在weka中打开测试集votetest.arff,观察到数据集共有435个实例,每个实例是一个国会议员的投票信息以及派别,共有17个二元属性,其中一个为类别属性。并且该数据集带有一定的缺失值。国会议员通常按照其党政路线进行投票,本实验通过对议员投票情况(16个属性)对其类别属性进行分类,得到两种派系对政策投票的大致方案。数据集中数据没有与实验无关属性,不进行过滤。

    4.2 使用C4.5决策树算法进行分类训练C4.5决策树算法能够处理具有缺省值的数据,使用信息增益率作为属性选择标准,能对生成树剪枝(参考《数据挖掘与机器学习—WEKA应用技术与实践》)。C4.5在weka中的实现是J48决策树。选择J48进行分类。




    训练结果
    使用C4.5决策树分类器训练数据集(435个实例),得到树形结构如上图所示,共有6个叶子节点。分类模型的准确率为97.2414%,正确分类的实例有423个,Kappa统计量为0.9418,平均绝对误差为0.0519,ROC面积为0.986;混淆矩阵中被错误分类的数据:6个republican被误分为democrat,6个democrat被误分为republican。
    测试:使用测试集进行预测



    预测结果
    预测准确率为95%,ROC面积为0.939,20个实例中有19个预测正确,一个错误。根据混淆矩阵得:一个republican被错误分类到democrat。
    4.3 基于规则的分类器进行分类训练分类模型的规则使用析取范式R=(r1 V r2 V … V rk),规则ri的形式:(Condition)->yi,规则左边是属性测试的合取,右边为预测类别。本实验采用的JRip分类器实现了命题规则学习,重复增量修剪以减少产生错误。(参考《数据挖掘与机器学习—WEKA应用技术与实践》)
    分类训练构建模型



    训练结果
    分类训练得到的规则共有4个。分类模型的准确率为96.5517%,正确分类的实例有420个,Kappa统计量为0.9277,平均绝对误差为0.0615,ROC面积为0.976;混淆矩阵中被错误分类的数据:10个republican被误分为democrat,5个democrat被误分为republican。
    预测



    预测结果
    预测准确率为95%,ROC面积为0.939,20个实例中有19个预测正确,一个错误。根据混淆矩阵得:一个republican被错误分类到democrat。
    4.4 基于K最近邻算法的分类器进行分类训练通过找出与测试样本相近的训练样本,用最近邻的类别标签确定测试样本的类别标签。IBK分类器是一种k-最邻近分类器,可用多种不同搜索算法加快寻找最近邻。(参考《数据挖掘与机器学习—WEKA应用技术与实践》)



    训练结果
    K-最邻近分类模型的准确率为99.7701%,正确分类的实例有434个,Kappa统计量为0.9951,平均绝对误差为0.0049,ROC面积为1.000;混淆矩阵中被错误分类的数据:1个democrat被误分为republican。
    预测



    预测结果:对20个实例的预测全部正确,预测正确率为100%。
    五、实验分析
    比较分析:在本实验中KNN算法相比于C4.5决策树、规则分类具有更好的分类效果。
    六、实验总结根据议员对各个法案的投票,采用KNN算法可以进行更准确的分类,并根据分类模型可以大概率地推测出议员所属党系。一个议员对法案的投票通过与否基本不会偏离所属党派的主要策略。那么一个议员的属性在特征空间里相似的样本中大多属于某一类,则说明其观点大多一致,属于同一党派。KNN算法对这种党派分类与现实符合,从实例具有的全部属性进行判断。而决策树以及规则的分类模型条件划分是对个别属性是否来判断确定,但是对党派的划分条件不应该只根据局部的几个属性进行判断,所以从现实角度看这两种算法也不合适。
    0 留言 2020-07-15 17:21:52 奖励26点积分
  • 【课程笔记】南大软件分析课程12——Soundiness


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

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

    目录
    Soundness & Soundiness复杂语言特性一:Java Reflection复杂语言特性二:Native Code
    重点理解soundiness的含义,为什么要引入它?
    理解为什么Java reflection和native code分析这么复杂。
    课程就这么结束了,抽象解释可能要在研究生课程再讲。
    分析真实复杂程序时,产生的问题都与Soundiness有关,是最前沿的topic之一。
    1.Soundness & SoundinessSoundness:保守估计,分析结果能包含程序所有可能的执行。学术界和工业界都做不到。
    复杂语言特性:导致分析结果不精确。

    Java:Reflection, native code, dynamic class loading, etc.
    JavaScript:eval(执行任意命令), document object model (DOM,和DOM加护), etc.
    C/C++:Pointer arithmetic(指针地址+1或乘以), function pointers, etc.

    现状:有些文章不提这类问题,或者随意一提(如eval)。极具误导性,导致相信该工具很sound,且影响专家的评判。
    Soundiness:直观相信的”truth”,但没有任何事实和证据。
    词语对比:

    sound analysis:能捕捉所有动态运行行为,理想化。
    soundy analysis:目标是捕捉所有动态行为,但对于某些复杂语言特性可以unsound。
    unsound analysis:为了效率、精度,故意不处理某些行为。

    2.复杂语言特性一:Java Reflection—反射(1)介绍Java反射Java Reflection:反射机制很重要的一点就是“运行时”,其使得我们可以在程序运行时加载、探索以及使用编译期间完全未知的 .class 文件。换句话说,Java 程序可以加载一个运行时才得知名称的 .class 文件,然后获悉其完整构造,并生成其对象实体、或对其 fields(变量)设值、或调用其 methods(方法)。

    说明:无反射代码在编译时就能确定对象;反射代码在运行时才确定对象,如c指向什么,”Person”也可能是的字符串指针,很难静态分析。分析该类代码很有必要,如弄清对象到底调用了哪个目标函数、对象域的指向关系等。
    (2)分析方法分析方法:String Contant analysis + Pointer Analysis(Reflection Analysis for Java——APLAS 2005)。
    示例:目标是分析m调用的目标函数。

    找到m的定义点,即Method m = c.getMethod(mName, ...);
    通过String Contant analysis找到mName指向内容
    通过指针分析找到c指向内容
    通过String Contant analysis找到cName指向内容
    知道了是调用Person类的setName函数


    问题:若字符串的值无法通过静态分析得到,则反射目标不能求解。Eg,字符串来自配置文件、网络、命令行、复杂字符串处理、动态生成、加密。
    (3)改进解决方法:Type Inference + String analysis + Pointer Analysis(Self-Inferencing Reflection Resolution for Java——ECOOP 2014,李樾,谭添老师的成果)。在创造点不可推,但在使用点可推。
    示例:类名依赖cmd参数,解不出来;但在调用点,通过Java的类型系统推导parameters,发现parameters是this指针。推出结论就是,175行的目标函数有1个参数,且声明类型要么是FrameworkCommandInterpreter要么是其子类。结果推断出50个反射目标函数,48个为true。

    最新工作:Understanding and Analyzing Java Reflection (TOSEM 2019) Yue Li, Tian Tan, Jingling Xue。不仅求解反射对象更准确更多,而且能说出哪里解的不准。
    常用方法:Taming reflection: Aiding static analysis in the presence of reflection and custom class loaders (ICSE 2011)。利用动态分析来解,缺点是测试用例的覆盖路径有限,优点是只要解出来,结果都为真。
    3.复杂语言特性二:Native CodeNative Code:一个Native Method就是一个java调用非java代码的接口。该方法的实现由非java语言实现,已被编译为特定于处理器的机器码的代码,这些代码可以直接被虚拟机执行,与字节码的区别:虚拟机是一个把通用字节码转换成用于特定处理器的本地代码的程序,比如C。这个特征并非java所特有,很多其它的编程语言都有这一机制,比如在C++中,你可以用extern “C”告知C++编译器去调用一个C的函数。
    Java Native Interface(JNI):是一种编程框架(函数模型,反映参数格式等),使得Java虚拟机中的Java程序可以调用本地应用/或库,也可以被其他程序调用。 本地程序一般是用其它语言(C、C++或汇编语言等)编写的,并且被编译为基于本机硬件和操作系统的程序。
    示例:先加载Native库,声明Native函数,*env变量可以在Native代码中用于创建对象、访问域、调用Java中的方法等,支持230个JNI函数。问题是跨语言之后,如何静态分析je.guessMe()这个调用?

    方法:对重要的native code手动建模。例如,对经常调用的arraycopy()函数进行建模,建模后就是一个拷贝循环,但从指针分析角度来讲,看到这个循环,我们就把数组指针进行传递。

    最新工作:Identifying Java Calls in Native Code via Binary Scanning (ISSTA 2020)。通过扫描二进制程序来识别native code中的Java调用。
    扩展:想深入研究Soundiness,可参考网站http://soundiness.org 。
    参考Java 反射由浅入深 | 进阶必备
    java native方法使用
    0 留言 2020-09-10 10:35:22 奖励30点积分
  • 【课程笔记】南大软件分析课程11——CFL可达性&IFDS


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

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

    目录
    Infeasible and Realizable Paths——基本概念CFL-Reachablity(IFDS的理论基础,识别Realizable path)Overview of IFDSSupergraph(之前叫iCFG) and Flow FunctionsExploded Supergraph and Tabulation AlgorithmUnderstanding the Distributivity of IFDS
    重点IFDS:Interprocedural,Finite,Distributive,Subset Problem。
    理解CFL-Reachablity,工作机制—括号匹配的过程。
    IFDS的大致原理。
    哪些问题可以利用IFDS,目标问题是否可以利用IFDS,取决于其是否满足可分配性。
    目标:以图可达性分析来进行程序分析,没有了数据流传播的过程。
    1.Infeasible and Realizable Paths——基本概念Infeasible Paths:CFG中实际不会执行到的路径,如不匹配的调用返回边。这种路径可能会影响到程序分析的结果,但静态分析不能完全判定路径是否可达。
    Realizable Paths:跨函数调用产生的返回边和对应的callsite边匹配,这样的path。

    目标:识别Realizable path,避免沿着Unrealizable path来传播数据分析。
    方法:CFL-Reachablity。

    2.CFL-Reachablity(IFDS的理论基础,识别Realizable path)CFL-Reachablity:path连接A和B,或者说A能到达B,当且仅当path所有边的labels连接起来 是context-free language(CFL)中的一个word(或者说经过CFG语法变换之后可以得到该path word)。CFL是编译原理中的概念,遵循CFG语法。
    Context-Free Grammar (CFG):CFG是一个形式化语法,每一个产生的形式都是 S→αS \to \alphaS→α(α\alphaα可以是字符串也可以是空ε\varepsilonε)。EgEgEg,S→aSbS \to aSbS→aSb,S→εS \to \varepsilonS→ε;Context-Free表示不管S出现在哪(不管上下文),S都可以被替换成aSb/εaSb / \varepsilonaSb/ε。
    部分括号匹配问题(Partially Balanced-Parenthesis):利用CFL来解决括号匹配问题,以识别Realizable path。

    部分——有)i一定要有(i,反之有(i不一定要有)i,也即可以调用子函数而不返回。
    标记,调用边——(i;返回边——)i;其他边——e。


    CFL-Reachablity:若path word(所有edge的label连起来组成的单词)可用CFL L(realizable)表示(可进行各种替换),则为Realizable Path。示例如下,(1(2e)2)1(_1(_2e)_2)_1(​1​​(​2​​e)​2​​)​1​​(3就是边的label相连接形成的,绿色是可匹配的部分,realizable可被替换为matched realizable、(i realizable、ε\varepsilonε。语法替换规则如下,这也是一个CFL语言示例:

    利用CFL分析Realizable Path示例:右边显然不是Realizable Path。

    3.Overview of IFDSIFDS含义:Interprocedural,Finite,Distributive,Subset Problem。Interprocedural—全程序分析,Finite—域有限(如live variables、definitions),Distributive—Transfer Function满足f(a∪b)=f(a)∪f(b)f(a \cup b)=f(a) \cup f(b)f(a∪b)=f(a)∪f(b),Subset—子集问题。
    利用图可达性的程序分析框架:采用的操作——Meet-Over-All-Realizable-Paths(MRP),MRPn⊑MOPnMRPn \sqsubseteq MOPnMRPn⊑MOPn。MOP对所有路径进行meet操作,MRP只对realizable path进行meet操作,更准确。
    IFDS步骤:给定程序P,数据流分析问题Q。

    1.构造P的supergraph G∗G^*G​∗​​,根据问题Q定义G∗G^*G​∗​​上每条边的流函数。
    2.构造P的exploded supergraph G♯G ^ \sharpG​♯​​,将流函数转化为Representation relation(分解后变成小子图形式)
    3.问题Q变成图可达性问题(寻找MRP解),对G♯G ^ \sharpG​♯​​采用Tabulation算法。n—程序点,data fact d∈MRPnd \in MRPnd∈MRPn,当且仅当G♯G ^ \sharpG​♯​​中存在一条<Smain,0>→<n,d><Smain, 0> \to <n, d><Smain,0>→<n,d>的 realizable path。


    4.Supergraph(之前叫iCFG) and Flow Functions(1)IFDS步骤一:构造Supergraph说明:之前叫iCFG,给每个node定义transfer function;现在叫做Supergraph,给每个edge定义transfer function。
    Supergraph:G∗=(N∗,E∗)G^*=(N^*, E^*)G​∗​​=(N​∗​​,E​∗​​)。

    G∗G^*G​∗​​包含所有的流图G1G_1G​1​​, G2G_2G​2​​, … (每个函数对应一个流图,本例对应GmainG_{main}G​main​​和GpG_pG​p​​);
    每个流图GpG_pG​p​​都有个开始节点sps_ps​p​​和退出节点epe_pe​p​​;
    每个函数调用包含调用节点CallpCall_pCall​p​​ + 返回节点RetpRet_pRet​p​​。
    函数调用有3类边:

    过程内call-to-return-site边,从Callp→RetpCall_p \to Ret_pCall​p​​→Ret​p​​;
    过程间call-to-start边,从Callp→spCall_p \to s_pCall​p​​→s​p​​(sps_ps​p​​是被调用函数的开头);
    过程间exit-to-return-site边,从ep→Retpe_p \to Ret_pe​p​​→Ret​p​​(epe_pe​p​​是被调用函数的结尾)。



    (2)IFDS步骤一:设计流函数问题Q:假设问题Q是找可能未被初始化的变量,对每个节点n∈N∗n \in N^*n∈N​∗​​,找到执行到n时可能未被初始化的变量集合。
    说明:λ\lambdaλ——lambda 中’.’左侧的S表示输入的集合,右边表示对S的操作。对于未初始化变量问题,遇到var x;指令则 λS.S∪x\lambda S.S \cup {x}λS.S∪x—加入x变量;如遇x:=...;指令则λS.S−x \lambda S.S-{x}λS.S−x—去掉x;遇到无关指令则λS.S \lambda S.SλS.S—不变。
    示例:

    call-to-callee把与callee直接相关信息传递进去,如用形参替换实参;
    exit-to-return边把形参相关信息剔除;
    call-to-return-site只传递局部变量,排除全局变量g,降低误报。全局变量已经传入到被调用函数进行处理了,全局变量是否被初始化取决于被调用函数。


    5.Exploded Supergraph and Tabulation Algorithm(1)IFDS步骤二:构造exploded supergraphExploded Supergraph G♯G ^ \sharpG​♯​​:将trans func转换成边的关系representation relations(graph),每个流函数变成了有2(D+1)个节点,边数最多(D+1)2,D表示dataflow facts元素个数(如待分析的变量个数)。G∗G^*G​∗​​中每个结点n被分解成D+1个结点,每条边n1→n2n_1 \to n_2n​1​​→n​2​​被分解成representation relation。
    representation relation:用Rf表示,流函数-f。Rf⊆(D∪0)×(D∪0)R_f \subseteq (D \cup 0) \times (D \cup 0)R​f​​⊆(D∪0)×(D∪0)。RfR_fR​f​​规则如下:

    0→00 \to 00→0始终有一条边;
    0→d10 \to d_10→d​1​​,y∈f(∅)y \in f( \varnothing)y∈f(∅) 若没有任何输入也能得到y,则加上该边;
    d1→d2d_1 \to d_2d​1​​→d​2​​,y可以从x得到,但不能从0得到,则加上该边;
    还有一条,di→did_i \to d_id​i​​→d​i​​,与did_id​i​​无关时自己连自己,保持可达性。

    示例:
    (1)输入S是什么输出就是什么,1/3;
    (2)无论什么输入,都输出{a},1/2;
    (3)b是无条件产生,所以0→b,a不能往下传了,b已经从0可达了就不用加b→b,c不受影响,也即无论有关a和b的事实之前是什么样,都不再重要;
    (4)b通过a得到所以a→b,不影响a、c的传递。注意,这里的值不是说变量在程序中真正的值是多少,而是说有关此变量的数据流事实的值是什么,如a的值可以为被初始化了和未被初始化两种,对应的集合即不包括和包括a。

    问题:为什么需要0→00 \to 00→0的边?以往数据流分析中,确定程序点(结点)p是否包含data fact a,是看a是否在OUT[p]中;IFDS中,是看<smain,0><s_{main}, 0><s​main​​,0>是否能到达<p, a>。如果没有0→00 \to 00→0的边,则无法完全连通,所以0→00 \to 00→0又称为Glue Edge。
    构建G♯G^ \sharpG​♯​​示例:最后能从<smain,0>→<emain,g><s_{main}, 0> \to <e_{main}, g><s​main​​,0>→<e​main​​,g>(要通过realizable paths),则emaine_{main}e​main​​点的g是可能未初始化的。emaine_{main}e​main​​处的x和nPrint(a,g)n_{Print(a,g)}n​Print(a,g)​​处的g都是初始化过的,因为从smains_{main}s​main​​不可达(不能通过non-realizable paths——绿色线)。



    (2)IFDS步骤三:Tabulation算法——判断是否可达说明:实心圈表示从<smain,0><s_{main}, 0><s​main​​,0>通过realizable paths可达,空心圈表示不可达。
    目标:给定exploded supergraph G♯G^ \sharpG​♯​​,Tabulation算法通过寻找从<smain,0><s_{main}, 0><s​main​​,0>的所有realizable paths来确定MRP解。也即n—程序点,data fact d∈MRPnd \in MRPnd∈MRPn,当且仅当G♯G^ \sharpG​♯​​中存在一条<Smain,0>→<n,d><S_{main}, 0> \to <n, d><S​main​​,0>→<n,d>的realizable path。
    Tabulation算法:复杂度是O(ED3)O(ED^3)O(ED​3​​),E—supergraph的边数,D是域中待分析元素的个数。主要工作:括号匹配+路径探索。主要就是处理调用边、返回边、总结边,将间接可达的两结点直接连起来,每个结点用Xn存储当前所有可达的data fact。

    calledProc: 把函数调用结点(call)和代表被调用函数名关联上
    returnSite: 把call结点和return结点连起来
    callers: 把函数名映射到call结点所形成的集合关联
    procOf: 把函数结点和它的函数主体关联


    Tabulation算法工作原理:假设只关注1个data fact,p’被p和p’’同时调用。

    处理括号匹配:每次处理到返回点ep′e_{p^{\prime}}e​p​′​​​​时,开始括号匹配(call-to-return匹配),找到调用点(Callp,Callp′′)(Callp, Call{p^{\prime \prime}})(Callp,Callp​′′​​)和相应的返回点(Retp,Retp′′)(Retp, Ret{p^{\prime \prime}})(Retp,Retp​′′​​)。
    处理总结边——SummaryEdge:总结边—<Call,dm>→<Ret,dn><Call,d_m> \to <Ret,d_n><Call,d​m​​>→<Ret,d​n​​>,表示dmd_md​m​​通过调用p′p^{\prime}p​′​​能到达pnp_np​n​​,要避免重复处理ppp和p′′p^{\prime \prime}p​′′​​中调用同一函数p′p^{\prime}p​′​​(优化)。


    Tabulation算法优点:传统的worklist算法是利用了queue的特性,每次循环只考虑与被改变值结点的相关结点。论文中用于解决图可达问题的Tabulation 算法是基于worklist的动态规划算法,比传统worklist算法考虑interprocedure问题更精确也更省时。
    6.Understanding the Distributivity of IFDS问题:不能用IFDS进行常量传播分析、指针分析。
    原因:由IFDS的框架决定,一次只能处理1个变量。例如,表示若x和y都存在则…,无法表示这种关系。不满足F(x^y)=F(x)^F(y)。
    总结:给定语句S,如果输出取决于多个输入的data fact,则该分析不具备可分配性,不能用IFDS表达。IFDS中,每个data fact(圆圈)与其传播(边)都可以各自处理,且不影响最终结果。
    指针分析:箭头表示变量是否指向new T,但由于缺乏别名信息alias(x,y) / alias(x.f,y.f),导致分析结果错误。归根结底,要想在IFDS中获取别名信息alias(x,y),需要考虑多个输入data fact(x、y),所以不能用IFDS。

    参考用求解图内节点是否可达的算法来解决IFDS问题
    0 留言 2020-07-22 10:12:37 奖励30点积分
  • 【课程笔记】南大软件分析课程10——基于Datalog的程序分析


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

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

    目录
    MotivationDatalog介绍Datalog实现指针分析Datalog实现污点分析
    重点Datalog语法,如何利用Datalog实现指针分析和污点分析。
    本节课内容讲到了很多数据逻辑方面的应用,单上数理逻辑会觉得理论性太强,单上这节课的应用知识又觉得理论上不够严谨,总之算是一种互补。
    1.Motivation内容:了解命令式 vs 声明式语言,对比两种语言实现指针分析算法的优劣。
    // 问题:从一群人中挑出成年人。// 命令式语言(Imperative):详细的命令机器怎么(How)去处理一件事情以达到你想要的结果(What)。如JavaSet<Person> selectAdults(Set<Person> persons) { Set<Person> result = new HashSet<>(); for (Person person : persons) if (person.getAge() >= 18) result.add(person); return result; }// 声明式语言(Declarative):只告诉你想要的结果(What),机器自己摸索过程(How)。如SQL,代码更简洁SELECT * FROM Persons WHERE Age >= 18;
    命令式语言—PTA:若采用命令式实现指针分析算法,实现复杂。需考虑worklist数据结构,是数组list还是链表,是先进先出还是先进后出;如何表示指针集合,hash集还是bit向量;如何关联PFG节点和指针;如何处理相关语句中的变量。

    声明式语言—PTA:如何用声明式语言实现PTA?优点是简洁、可读性强、易于实现,例如Datalog。缺点是不方便表达复杂逻辑(Eg,for all全部满足)、不能控制性能。
    2.Datalog介绍Datalog(Data + Logic):是声明式逻辑编程语言,可读性强,最初用于数据库。现在可用于程序分析、大数据、云计算。特点—没有副作用、没有控制流、没有函数、非图灵完备(精简了许多功能)。
    (1)Data(谓词、原子)谓词Predicate:看作一系列陈述的集合,陈述某事情是不是事实(真假)。如Age,表示一些人的年龄。
    事实fact:特定值的组合。Eg,(“Xiaoming”, 18)。

    原子Atom:P(X1, X2, ... , Xn)。P表示谓词名,Xi表示参数(又叫term,可以是变量或常量)。Eg,Age("Xiaoming", 18) == true ;Age("Alan", 23) == false。
    (2)Logic(Rule)Rule:表示逻辑推导规则,若Body都为true,则Head为true。H <- B1, B2, ... ,Bn。H是Head,Bi是Body。 Eg,Adult(person) <- Age(person, age), age >= 18。
    Rule要求:规则中的值要有限,如A(x) <- B(y), x > y;规则不能有悖论,如A(x) <- B(x), !A(x)。
    Datalog中逻辑或:A或B都可推导出C,可写成C<-A. C<-B或者C<-A;B。
    Datalog中逻辑非:!B(...)。
    (3)Datalog谓词分类
    EDB(extensional database)外延数据库:谓词需预先定义,关系不可变,可被当做输入。
    IDB(intensional database)内涵数据库:谓词是根据规则建立的,关系是根据规则推导的,可被看作是是输出。

    说明:H <- B1, B2, ... ,Bn,H只能是IDB,Bi可以是EDB或IDB。
    递归性:Datalog支持递归,也即能够推导出自身。Eg,Reach(from, to) <- Edge(from, to);Reach(from, to) <- Reach(from, node), Edge(node, to)。
    (4)Datalog程序运行Datalog程序运行:输入EDB+rules到Datalog引擎,输出IDB。常用Datalog引擎——LogicBlox, Soufflé, XSB, Datomic, Flora-2。
    Datalog程序性质:单调性、终止性。
    3.Datalog实现指针分析(1)概念EDB:程序句法上可获得的指针相关信息。如New / Assign / Store / Load语句。V-变量,F-域,O-对象。

    New(x: V,o: O) <- i: x = new T()
    Assign(x : V, y : V) <- x=y
    Store(x : V, f : F, y : V) <- x.f = y
    Load(y : V, x : V, f : F) <- y = x.f

    IDB:指针分析结果。

    VarPointsTo(v: V, o : O) ,如VarPointsTo(x,oi)表示oi ∈ 𝑝𝑡(𝑥)
    FieldPointsTo(oi : O, f: V, oj : O) ,如FieldsPointsTo(𝑜i, 𝑓, 𝑜j)表示𝑜j ∈ 𝑝𝑡(𝑜i.𝑓)

    Rules:指针分析规则(与之前相同)。先分析上下文不敏感。

    (2)上下文不敏感PTA示例
    步骤:其实指令处理顺序不固定。

    首先将EDB(指令)表示成表格数据形式。
    处理New指令
    处理Assign指令
    处理Store指令
    处理Load指令

    (3)上下文敏感—全程序指针分析call指令规则:S—指令,M—方法。共3条rule。
    1.首先找到调用的目标函数m,传递this指针。

    2.传递参数

    3.传返回值

    全程序指针分析:引入程序入口函数m。

    4.Datalog实现污点分析EDB谓词-输入:

    Source(m : M) ——产生污点源的函数
    Sink(m : M) ——sink函数
    Taint(l : S, t : T) ——关联某callsite l和它产生的污点数据t

    IDB谓词-输出:

    TaintFlow(t : T, m : M) ——表示污点数据t会流向sink函数m
    规则:处理source和sink函数。

    课后问题
    有的调用图有多个main入口方法,咋办?将多个入口函数都加入到EntryMethod(m)即可。
    有没有datalog和传统结合的做法如chord(java+Datalog实现)
    0 留言 2020-07-21 15:56:32 奖励30点积分
显示 60 到 75 ,共 15 条

热门回复

  • 基于SSM的超市订单管理系统
    感谢分享,非常棒的开发
    2020-08-30 14:43:15 thumb_up( 3 )
  • 基于SSM的超市订单管理系统
    可以用吗,怎么用的
    2021-04-14 15:44:50 thumb_up( 1 )
  • 线程同步之临界区
    程序还算比较简单的,谢谢分享
    2019-04-20 12:24:58 thumb_up( 1 )
  • 基于WinPcap实现的UDP发包程序
    如果在vs 编译时出现 无法找到元数据文件 platform.winmd 应该怎么解决
    2021-03-23 09:58:16 thumb_up( 2 )
  • 机器视觉MIL Mod匹配
    You can also search within the full angular range of 360� from the nominal angle specified with M_ANGLE. Use the MmodControl()�M_ANGLE_DELTA_POS and M_ANGLE_DELTA_NEG control types to specify the angular range in the counter-clockwise and clockwise direction from the nominal angle, respectively; the default for both is 180�. The angular range limits the possible angles which can be returned as results for an occurrence. Note that the actual angle of the occurrence does not affect search speed. If you need to search for a model at discrete angles only (for example, at intervals of 90 degrees), it is typically more efficient to define several models with different expected angles, than to search through the full angular range. By default, calculations specific to angular-range search strategies are enabled. If you expect that the occurrences sought are close to the specified nominal angle, you can disable these calculations using MmodControl() with M_SEARCH_ANGLE_RANGE set to M_DISABLE. When disabled, you must specify a good nominal angle for each model, which is within the model's angular range. You can restrict which candidates are returned as occurrences by narrowing the angular-range. Note that M_SEARCH_ANGLE_RANGE must be enabled to search for a rotation-invariant non-synthetic model (for example, an image-type model of a circle).
    2021-03-20 13:27:51 thumb_up( 2 )
eject