防火墙算法设计与开发(课程设计)

1课程设计2防火墙规则分析、翻译的算法研究随着互联网的发展，网络安全问题已经引起了学术界和工业界的广泛重视。随着来自网络的攻击持续不断的增长，防火墙已经成为网络安全领域的一种核心设备，并广泛应用于企业网络和小型的家庭网络。作为安全网络抵御攻击和过滤未经授权数据流的前沿设备，防火墙的过滤决策是基于根据预先定义的安全策略而形成的一组有序的过滤规则。虽然防火墙的成功部署是保证网络安全的重要一步，但成功部署并不意味着就可以理所当然的获得相应的安全保障，这是因为防火墙安全规则管规则数目的增多，不可避免的会出现下面两个问题：（1）随着规则复杂度的增加，规则也变得难以理解，当维护规则集的人员变更时，会使规则集的维护变得很困难。（2）当对规则集中的规则进行删除、修改或者添加规则时，大量的过滤规则中可能存在冗余的规则，导致防火墙的管理难度加大、吞吐率下降。所以就有必要在实施安全策略之前，对过滤规则进行必要的分析，发现并纠正其中的冗余，而且最好能为网络管理人员提供相应的工具，帮助其完成安全策略的管理工作。余的算法，以定位冗余的规则，使得管理人员不用在大量的规则里手工查找冗余，同时给出了导致冗余的网络安全是指网络系统的硬件、软件及其系统中的数据受到保护，不因偶然的或者恶意的原因而遭受到破坏、更改、泄露，系统连续可靠正常地运行，网络服务不中断。网络安全从其本质上来讲就是网络上的信息安全。从广义来说，凡是涉及到网络上信息的保密性、完整性、可用性、真实性和可控性的相关信息安全技术、应用数学、数论、信息论等多种学科的综合性学科。在社会日益信息化的今天，信息已成为一种重要的战略资源，信息的应用也从原来的军事、科技、文化和商业渗透到当今社会的各个领域，其在社会生产、生活中的作用日益显著。传播、共享和自增值是信息的固有属性，与此同时，又要求信息的传播是可控的，共享是授权的，增值是确认的。因此信息的安全和可靠在任何状况下都是必须要保证的。信息网络的大规模全球互联趋势，Internet的开放性，以及人们的社会与经济活动对计算机网络依赖性的与日俱增，使得计算机网络的安全性成为信息化建设的一个核以Internet为代表的信息网络技术的应用正日益普及和广泛，应用层次正在深入，应用领域从传统的小型业务系统，逐渐向大型关键业务系统扩展，典型的如党政部门信息系统、金融业务系统、企业商务系统等。伴随网络的普及，安全日益成为影响网络效能的重要问题，而Internet所具有的开放性、国际性和自由性在增加应用自由度的同时，对安全提出了更高的要求，这主要表现在：因而网络所面临的破坏和攻击可能是多方面的。例如，来自物理传输线路的攻击能对网络通信协议和实现（2）国际性的一个网络还意味着网络的攻击不仅仅来自本地网络的用户，它可以来自Internet上的任何一个机器，也就是说，网络安全所面临的是一个国际化的挑战。3（3）自由意味着网络最初对用户的使用并没有提供任何的技术约束，用户可以自由地访问网络，自由地使用和发布各种类型的信息。用户只对自己的行为负责，而没有任何的法律限制。尽管开放的、自由的、国际化的Internet的发展给政府机构、企事业单位带来了革命性的改革和开放，使得他们能够利用Internet提高办事效率和市场反应能力，以便更具竞争力。通过Internet，他们可以从异地取回重要数据，同时又要面对网络开放带来的数据安全的新挑战和新危险。如何保护企业的机密信息不受黑客和工业间谍的入侵,已成为政府机构、企事业单位信息化健康发展所要考虑的重要事情之一。2.2.1非授权访问统进行违法操作；合法用户以未经授权方式进行操作等。2.2.2欺骗类攻击或网络的弱点来实现。信息传输安全问题有四种基本类型，如图2.1所示。信息源节点信息源节点截获非法用户信息目的节点信息源节点信息目的节点非法用户信息源节点信息目的节点信息源节点信息目的节点篡改伪造非法用户非法用户图2.1信息传输安全问题的四种基本类型2.2.4计算机病毒性、衍生性、不可预见性和破坏性等特性，而且在网络中其危害更加可怕，目前可通过网络进行传播的病毒已有数万种，可通过注入技术进行破坏和攻击。42.2.5软件漏洞随着软件系统规模的不断增大，系统中的安全漏洞也不可避免的存在而且也在不断增多。比如常用的操作系统，无论是Windows还是UNIX几乎都存在或多或少的安全漏洞，众多的各类服务器、浏览器及其它常用的软件等也都不同程度的存在着安全隐患。2.2.6恶意攻击当今最突出的就是拒绝服务攻击DoS（DenialofService）。它通过使计算机提供服务。典型拒绝服务攻击有资源耗尽和资源过载两种。2.3.1防火墙技术防火墙是建立在两个网络边界上的实现安全策略和网络通信监控的系统或系统集，它强制执行对内部均衡负载等。它已经成为目前保护内部网络最重要的安全技术之一。2.3.2漏洞检测技术漏洞检测就是对重要计算机系统或网络系统进行检查，发现其中存在的薄弱环节和所具有的攻击性特口令以及其他同安全规则相背的对象进行检查；主动式策略基于网络检测，通过执行一些脚本文件对系统2.3.3入侵检测技术入侵检测技术用来对各种入侵行为进行检测，它通过对（网络）系统的运行状态进行监视，以发现各种攻击企图、攻击行为或者攻击结果，然后及时的发出报警或做出相应的响应，以保证系2.3.4防病毒技术防病毒技术主要是通过自身常驻系统内存，通过监视、判断系统是否存在病毒来阻止计算机病毒进行计算机系统，防止病毒对系统进行破坏，从而可以有效防止计算机病毒对系统造成的危害，3.1.1防火墙的定义防火墙是指设置在不同网络（如可信任的企业内部网络和不可信的公共网）或网络安全域之间的一系列部件的组合。它可以通过监测、限制、更改跨越防火墙的数据流结构和运行状况，以此来实现网络的安全保护。在原理上，防火墙是两种机制的组合：一种是阻断数据流，另一种是允许数据流。一些防火墙侧重于阻断数据流，另一些防火墙侧重于允许数据流。在逻辑上，防火墙是一个分离器、一个限制器，也是一个分析器，有效地监控了内部网和Internet之间的任何活动，保证了内部网络的安全。从该网络上对我们的网络发起攻击，破坏网络安全。对网络的保护包括下列工作：拒绝未经授权的用户访问，阻止未经授权的用户存取敏感数据，同时允许合法用户不受妨碍的访问网络资源。3.1.2防火墙的作用防火墙作为网络防护的第一道防线，它由软件或/和硬件设备组合而成，它位于企业或网络群体计算权限。防火墙是一种必不可少的安全增强点，它将不可信网络同可信任网络隔离开。防火墙筛选两个网络间5所有的连接，决定哪些传输应该被允许，哪些应该被禁止，这取决于网络制定的某一形式的安全策略。（1）服务控制：确定可以访问的网络服务类型。（2）方向控制：特定服务的方向流控制。（3）用户控制：内部用户、外部用户所需的某种形式的认证机制。（4）行为控制：控制如何使用某种特定的服务。在内部网络的应用中，经常会遇到内部网络用户擅自修改IP地址，以获取一个合法IP地址来进行相应的网络应用，这样会使内部网络在地址资源的分配和使用上出现混乱，大大影响内部网络的正常运行。更有甚者使用他人的地址在网络上发布非法信息、破坏网络安全，其影响将更为严重，而且，在网络事故发生以后，地址追寻的难度很大。为了防止这种地址盗用，防火墙提供了IP与MAC地址绑定的功能。IP与MAC的地址绑定规定一个IP只对应于某一特定的网卡（每个网卡具有唯一），上的规则相符，如果相符就放行，否则就不允许其通过防火墙。这样就大大方便了网络的IP地址管理。3.2.2网络地址转换技术（NAT）防火墙利用NAT技术能透明地对所有内部地址进行转换，使外部网络无法了解内部网络的内部结构，同时允许内部网络使用自己定制的IP地址和专用网络，防火墙能详尽记录每一个主机的通信，确保每个部网络的安全性。而且，NAT的另一个显而易见的用途是解决IP地址匮乏的问题。3.2.3多级过滤技术为保证系统的安全性和防护水平，防火墙采用了三级过滤措施。在分组过滤一级，能过滤所有的源路由分组和假冒的IP源地址；在应用级网关一级，能利用FTP、SMTP等各种网关，控制和监测Internet提供的所用能用服务；在电路网关一级，实现内部主机与外部站点的透明连接，并对服务的通行实行严格控3.2.4审计和警告防火墙的审计和告警功能十分健全，日志文件包括：一般信息、内核信息、接收邮件、数据备份与保全等方面具有特色。具有许多内置的能力，使开发人员可以根据自己的需要定制其工具、行为和外观，而无需昂贵的第三方工具。Netfilter/Iptables是与最新的2.4.x版本Linux内核集成的IP信息包过滤系统。如果Linux系统连接到因特网或LAN、服务器或连接LAN和因特网的代理服务器，则该系统有利于在Linux系统上更好地控制IP信息包过滤和防火墙配置。系统是最新的解决方案，而且也是第一个集成到Linux内核的解决方案。对于Linux系统管理员、网络管理员以及家庭用户（他们想要根据自己特定的需求来配置防火墙、在防火墙解决方案上节省费用和对IP信息包过滤具有完全控制权）来说，Netfilter/Iptables系统十分理想。虽然Netfilter/IptablesIP信息包过滤系统被称为单个实体，但它实际上由两个组件Netfilter和6Netfilter组件也称为内核空间（kernelspace是内核的一部分，由一些信息包过滤表组成，这些表包含内核用来控制信息包过滤处理的规则集。Iptables组件是一种工具，也称为用户空间（userspace它使插入、修改和除去信息包过滤表中的4.2.1配置防火墙和信息包过滤对于连接到网络上的Linux系统来说，防火墙是必不可少的防御机制，它只允许合法的网络流量进出系统，而禁止其它任何网络流量。为了确定网络流量是否合法，防火墙依靠它所包含的由网络或系统管理员预定义的一组规则。这些规则告诉防火墙某个流量是否合法以及对于来自某个源、至某个目的地或具有某种协议类型的网络流量要做些什么。术语“配置防火墙”是指添加、修改和除去这些规则。—组成。这些信息包有头，即在每个包前面所附带的一些数据位，它们包含有关信息包的源、目的地和协议类型的信息。防火墙根据一组规则检查这些头，以确定接受4.2.2Netfilter/Iptables的工作原理Netfilter/IptablesIP信息包过滤系统是一种功能强大的工具，可用于添加、编辑和除去规则，这些规则是在做信息包过滤决定时，防火墙所遵循和组成的规则。这些规则存储在专用的信息包过滤表中，型的信息包做些什么。如果某个信息包与规则匹配，那么使用目标ACCEPT允许该信息包通过。还可以使用目标DROP或REJECT来阻塞并杀死信息包。对于可对信息包执行的其它操作，还有许多其它目标。根据规则所处理的信息包的类型，可以将规则分组在链中。处理入站信息包的规则被添加到INPUT链中。处理出站信息包的规则被添加到OUTPUT链中。处理正在转发的信息包的规则被添加到FORWARD链中。这三个链是基本信息包过滤表中内置的缺省主链。另外，还有其它许多可用的链的类型（如PREROUTING和POSTROUTING以及提供用户定义的链。每个链都可以有一个策略，它定义“缺省目标”，也就是要执建立规则并将链放在适当的位置之后，就可以开始进行真正的信息包过滤工作了。这时内核空间从用这个过程称为路由。（1）如果信息包源自外界并前往系统，而且防火墙是打开的，那么内核将它传递到内核空间信息包（2）如果信息包源自系统内部或系统所连接的内部网上的其它源，并且此信息包要前往另一个外部（3）如果信息包源自外部系统并前往外部系统接下来，将信息包的头信息与它所传递到的链中的每条规则进如果信息包与某条规则匹配，那么内核就对该信息包执行由该规则的目标指定的操作。但是，如果信息包与这条规则不匹配，那么它将与链中的下一条规则进行比较。最后，如果信息包与链中的任何规则都不匹4.1用图形说明了这个信息包过滤过程。74.3.1规则的建立通过向防火墙提供有关对来自某个源、到某个目的地或具有特定协议类型的信息包要做些什么的指令，规则控制信息包的过滤。通过使用Netfilter/Iptables系统提供的特殊命令iptables，建立这些规则，并将其添加到内核空间的特定信息包过滤表内的链中。关于添加／除去／编辑规则的命令的一般语法4.3.2表（table）[-ttable]选项允许使用标准表之外的任何表。表是包含仅处理特定类型信息包的规则和链的信息包它包含PREROUTING、OUTPUT和POSTROUTING链。如果信息包及其头内进行了任何更改，则使用mangle链由指定信息包一到达防火墙就改变它们的规则所组成，而POSTROUTING链由指定正当信息包打算离开防火墙时改变它们的规则所组成。4.3.3命令（command）上面这条命令中具有强制性的command部分是iptables命令的最重要部分。它告诉iptables命令要-A或--append：该命令将一条规则附加到链的末尾。-D或--delete：该命令从链中删除指定要匹配的规则或者在链中某指定编号的规则。制使用此链的策略。-N或--new-chain：用命令中所指定的名称创建一个新链。-F或--flush：如果指定链名，该命令删除链中的所有规则，如果未指定链名，该命令删除所有链中-L或--list：列出指定链中的所有规则。4.3.4匹配（match）8源端口、目的端口和协议）。匹配分为两大类：通用匹配和特定于协议的匹配。这里，我将研究可用于采用任何协议的信息包的通用匹配。下面是一些重要的且常用的通用匹配：-p或--protocol：该通用协议匹配用于检查某些特定协议。协议示例有TCP、UDP、ICMP用逗号分隔-s或--source：该源匹配用于根据信息包的源IP地址来与它们匹配。该匹配还允许对某一范围内的IP地址进行匹配，可以使用!符号，表示不与该项匹配。缺省源匹配与所有IP地址匹配。-d或--destination：该目的地匹配用于根据信息包的目的地IP地址来与它们匹配。该匹配还允许对某一范围内IP地址进行匹配，可以使用!符号，表示不与该项匹配。还有许多可用的目标选项。下面是常用的一些目标：），停止遍历链（虽然该信息包可能遍历另一个表中的其它链，并且有可能在那里被丢弃）。该目标被指定为-jACCEPT。DROP：当信息包与具有DROP目标的规则完全匹配时，会阻塞该信息包，并且不对它做进一步处理。该目标被指定为-jDROP。REJECT：该目标的工作方式与DROP目标相同，但它比DROP好。和DROP不同，REJECT不会在服务器和客户机上留下死套接字。另外，REJECT如INPUT之类的主链，则使用该链的缺省策略处理信息包。它被指定为-jumpRETURN。4.3.6保存规则用上述方法所建立的规则会被保存到内核中，当重新引导系统时，就会丢失。如果将没有错误的且有可以使用iptables-save命令：iptables-save>iptables-script。现在，信息包过滤表中的所有规则都被保存在文件iptables-script中。无论何时再次引导系统，都可以使用iptables-restore命令将规则集从该脚本文件恢复到信息包过滤表：iptables-restore<iptables-script。本文只涉及到数据包过滤，即filter表。为了方便讨论，做出了以下简化。本文以后的论述，都是规则表中只包含filter表的过滤规则，不含nat表和mangle表的规则过滤规则中只有INPUT链匹配条件只包含源地址和目的地址规则目标只包含ACCEPT和DROP因防火墙规则表中的规则是顺序检测的，因此规则表中的顺序是非常重要的，前面的规则可以允许被后面的规则拒绝的数据包通过，反之不成立，如下的三条规则：iptables-AINPUT-shost1-jREJECTiptables-AINPUT-pTCP-dMAIL-dport25-jACCEPT第二条允许所有外部主机访问本地主机MAIL的25号端口；9虽然第二条允许所有外部主机访问本地主机MAIL的25号端口，但是第一条已阻止了来自host1的所iptables-AINPUT-pTCP-dMAIL-dport25-jACCEPTiptables-AINPUT-shost1-jREJECT此规则的语义为：允许所有外部主机访问本地主机MAIL的25号端口；禁止来自host1的其它连接。由上面可以看出，规则的顺序是非常重要的。两条规则的顺序调换以后，其语义已完全不同。为此，应在每条规则进入之前，将其翻译为自然语言，向用户显示，由用户判断语义的正确性。但每条规则的语义是与其在规则表中的位置紧密相关的，是与其上面的规则相联系的，所以首先将每条规则形式化，然后根据上面的规则对本条规则进行修正，最后，将其翻译成自然语言，显示给用户。这将完整地表达该条规则的语义，从而用户可判断是否符合其初衷，以决定本条规则是否可以录人。过滤规则可以看成是由所在规则表(table)，所在链(chain)，匹配条件(match)和目标(target)四部分组链，匹配条件(match)只包含源地址和目标地址，目标(target)只包含ACCEPT和DROP。于是可以做出以下定义1：规则形式化过滤规则为一个二元组（m，t表示对匹配m的信息包执行t操作。源、目的地址，源、目标端口等。根据4.4节的简化假设，这里m只包含（s，d）即源、目的地t代表目标（target）动作，为简化讨论，t∈（A，DA和D分别代表允许和拒绝。iptables-AINPUT-s87-d-jREJECT=。即r1=87，）,D）。5.3.1为什么进行规则相关性分析规则可能受很多在他之前的规则的影响。在规则翻译的时候，有必要考虑这些影响。例如以下规则：iptables-AINPUT-s87-d-jREJECTiptables-AINPUT-s64-d-jACCEPTiptables-AINPUT-s/24-jACCEPTr1=87，）,D）r2=64，）,A）r3=/24，）,A）r1阻止从87到的信r2接受从64到的信息包；r3接受从子网（即~55）来的信息包。以外的其他从子网来的信息包。规则的相关性分析就是为了找出所有和某5.3.2规则的相关性定义对规则进行观察可以发现，两条规则之间有联系也就意味着它们各自所匹配的信息包之间有交集。据相关子集：对规则r，规则集I中所有与r相关的规则的集合，被称作为规则r的相关子集，记为Relate(r)。另外对于Relate(r)中，位置在r前的规则的集合，被称作为规则r的前相关子集，记为PreRel(r)。5.3.3规则相关性的判定根据4.4节所做出的简化假设，可得出以下判定规则：r1~r2<=>r1.m∩r2.m≠<=>（r1.m.s∩r2.m.s≠)∧（r1.m.d∩r2.m.d≠)即两条规则相关当且仅当两条规则的匹配条件中的源地址和目标地址分别都有交集。根据5.3.2节的论述，规则的完整的语义应该考虑前面的规则对当前规则的影响。由于规则匹配的顺序性，到达当前规则的信息包必然不被前面的规则所匹配。所以，当前规则匹配的包的集合应该排除前面r1，r2，r3……r1.m（integrated）=r1.mr3.m（integrated）=~算法1：规则修正算法对第j条规则rjI，找出其前并与之相关的规则（即前相关规则集）算法1根据位置在其前的并且与之相关的规则对当前规则进行修正，得到完整的规则匹配条件。按照5.4节的方法得到修正后的规则表达式以后，就可以进行规则的自然语言翻译。在规则匹配条件r1=（r1.s∧r1.d，A）r3=（r3.s，D）r4=（r4.d，D）但是这种翻译方法存在一个缺点：当与当前规则相关的并且位置在其前的规则很多时，会生成很长的整的自然语言；当关闭该开关时，匹配条件过长的规则将只显示PreRel规则集中的规则有哪些。在增加防火墙规则时有可能造成其他某些规则的冗余。冗余的规则对防火墙的管理和性能都有负面的影（1）防火墙的管理方面：当网络管理员需要增加一些防火墙规则时，可能使别的防火墙规则冗余，可能使后面本来被冗余掉的规则重新有效，或者被删除的规则本来就是冗余的，以至管理员发现删除一条规则没有任何效果。冗余的规则会使防火墙规则的增加、删除、修改等操作产生意想不到的效果，增大了（2）防火墙的性能：冗余的规则在防火墙进行顺序匹配时，也会对到达它的信息包进行比较。这部但是，网络管理员要手工在大量的规则中寻找冗余的规则比较困难。因此希望通过本文的讨论可以让计算机自动对防火墙规则进行冗余检测，使管理员可以根据检测结果对防火墙作出相应的修改。能会有很多数据包和它匹配，条件是这些数据包的包头部分和这个规则的匹配项（match）相匹配。把这些数据包放到一起，构成一个集合，记为该规则的匹配集。iptables-AINPUT-s/24-jACCEPT6.3.1规则的包含性定义根据规则冗余的含义，规则的冗余和规则的匹配项之间的包含关系有紧密的联系。所以要确定一条规定义3：规则包含性如果r1，r2∈I，且r1.mr2.m，则称r1包含于r2，记为r1r2。6.3.2规则包含性的判定根据4.4节所做出的简化假设，可得出以下判定规则：r1r2<=>r1.mr2.m<=>（r1.m.sr2.m.s）∧（r1.m.dr2.m.d）即一条规则被另一条规则包含当且仅当一条规则的匹配条件中的源地址和目的地址分别都被另一条规则的源地址和目的地址包含。6.4.1规则的冗余判定本节在上一节规则包含性分析的基础上，分析两条具有包含关系的规则中，被包含的那一条规则是否下面分情况论述，请参看图6.1：假设r1，r2∈I，且r1在前r2在后，冗余规则检测是从前往后的I.如果r2r1，则匹配r2的包都将被r1处理，同时，其他的包都不被r2处理，故可以得出r2是冗余的2.其他情况不冗余，可作证明如下：a.当r1与r2之间有同r1相关的规则rh时，且rh.t=r1则这种情况在考虑r1与rh的冗余关系时，就会检测出r1或者rh为冗余则在考虑r1与rh的冗余关系时，就会得出r1不冗余的结论冗余结果r2冗余结果冗余结果冗余结果冗余结果B1Ab图6.1规则的冗余判定示意图根据以上的证明，可以总结出如下的判定：6.4.2规则的冗余检测在上一节中给出了定义4的冗余判定之后，则可以通过遍历规则表以找出所有的符合定义4的冗余规算法2：冗余检测算法从规则表中的第一条规则开始，对每一条规则ri则将rk从规则表中去掉，然后检查下一条ri后的规则则将ri从规则表中去掉，然后退出遍历ri后的规则检查下一条ri后的规则，直到规则表末尾检查下一条规则，直到规则表末尾取下一条规则对该规则进行形式化寻找该规则的前相关集否否是是输出完整的规则翻译是直接将该规则翻译前相关集的内容直接将该规则翻译为自然语言否图7.1规则翻译的算法流程图取下一条规则ri取ri后的下一条规则rk否否是将ri从规则表中去掉否最后一条规则？是将rk从规则表中去掉并输出rk是图7.2规则冗余的算法流程图7.3.1操作系统本文所讨论的Netfilter/Iptables是集成在Linux内核中的，所以应该在Linux操作系统上实现。但是由于条件限制，并且本文只关心算法的实现，故选用在大家常用的Windows操作系统中实现。7.3.2编程语言本文选用Java作为编程语言。由于Java中自带有很多类，方便用户直接调用；并且本文的核心算法采用链表的结构，用Java实现不需要设定指针，方便操作。7.3.3系统实现目标系统实现目标是提供一个分析规则的工具，该工具能对规则进行形式化并寻找该规则的前相关集。包含五个类，下面分别对每个类的属性及其函数进行分析。7.4.1规则集的链表类Listlength：用来存储链表的长度pointer：用来存储指向当前结点的前趋结点的指针,其值为null时表示当前结点是第一个结点insert(Noden)：插入函数。该函数在当前结点前插入一个结点，并使其成为当前结点。remove()：移除函数。删除当前结点同时返回其内容，并使其后继结点成为当前结点，如果删除的是最后一个结点，则第一个结点变为当前结点。cursor()：返回当前结点的指针currentNode()：用于返回当前结点的值。reset()：链表复位函数。该函数使链表中的第一个结点成为当前结点。deleteAll()：清空链表函数。用于清空整个链表。isEmpty()：判空函数。用于判断链表是否为空。isEnd()：用于判断当前结点是否为最后一个结点。size()：返回链表的大小7.4.2结点类结构Nodesource：用来存储规则的源地址destination：用来存储规则的目的地址target：用来存储规则的目标preRel：用来存储规则的前相关集next：用来存储当前规则的下一条规则即下一个结点Node(s,d,t,pr)：构造函数7.4.3前相关集的链表类ListPpHead：用来存储前相关集链表的头pTail：用来存储前相关集链表的尾pLength：用来存储前相关集链表的长度pPointer：用来存储前相关集链表中指向当前结点的前趋结点的指针,其值为null时表示当前结点是第一个结点insert(PreRele)：插入函数。该函数在当前结点前插入一个结点，并使其成为当前结点。其他函数与链表类List中的函数雷同，不一一说明。7.4.4相关集类结构PreRelSource、destination、targetpNext：用来存储当前结点的下一个结点PreRel(s,d,t)：构造函数7.4.5算法实现类结构Transparse_rule(e,l,a)和parse_rule(e)：形式化函数。对当前规则进行形式化，提取源地址、目的地址、目标；找出前相关集。并把这些属性存储到结点类中，这里调用了寻找前相关集的函数prerel(s,d,length,a)prerel(s,d,length,a)：寻找前相关集函数。求一条规则的前相关集，并以链表类型返回。这里调用了判断两条规则是否相关的函数is_relate(n1,source,destination)is_relate(n1,source,destination)：相关函数。用于判断两条规则是否相关，以布尔型返回。twoToTen(date)：进制转换函数。将整型或字节型的二进制ip地址转换为十进制值。创建链表取下一条规则对该规则进行形式化否插入到链表中是输出一条规则寻找该规则的前相关集否是否输出前相关集否是是输出无前相关集图7.3寻找前相关集的流程图 第11期6段海新，吴建平，李星.防火墙规则的动态分配和散列表匹配算法.清华大学学报（自然科学版）2001），import.InetAddress;classList//链表类，实现链表的基本操作{/*用变量来实现表头*/publicNodehead=null;publicNodetail=null;publicNodepointer=null;//存储指向当前结点的前趋结点的指针,当其值为null时表示当前结点是第一个结点publicvoiddeleteAll()/*清空整个链表*/{head=null;tail=null;pointer=null;}publicvoidreset()/*链表复位，使第一个结点成为当前结点*/{pointer=null;}publicbooleanisEmpty()/*判断链表是否为空*/{return(length==0);}publicbooleanisEnd()/*判断当前结点是否为最后一个结点*/{if(length==0)thrownewjava.lang.NullPointerException();returntrue;return(cursor()==tail);}publicNodecurrentNode()/*返回当前结点的值*/{Nodetemp=cursor();returntemp;}publicvoidinsert(Nodee){if(length==0){head=e;}{Nodetemp=cursor();e.next=temp;if(pointer==null)head=e;pointer.next=e;}}/*返回链表的大小*/{}publicNoderemove()/*删除当前结点同时返回其内容，并使其后继结点成为当前结点，如果删除的是最后一个结点，则第一个结点变为当前结点*/{Nodetemp;if(length==0)thrownewjava.util.NoSuchElementException();{temp=head;deleteAll();}{Nodecur=cursor();temp=cur;if(cur==head)head=cur.next;{pointer.next=null;tail=pointer;reset();}pointer.next=cur.next;}returntemp;}publicNodecursor()/*返回当前结点的指针*/{if(head==null)thrownewjava.lang.NullPointerException();elseif(pointer==null)returnhead;returnpointer.next;//前驱结点的下一个结点即当前节点}}classNode//构成链表的结点定义{Stringdestination;Stringtarget;ListPpreRel=null;//存储前相关集Nodenext;//用来存储当前规则的下一条规则即下一个结点Node(Strings,Stringd,Stringt,ListPpr)//构造函数{destination=d;target=t;preRel=pr;next=null;}}classListP//前相关集链表类{/*用变量来实现表头*/publicPreRelpHead=null;publicPreRelpTail=null;publicPreRelpPointer=null;publicintpLength=0;publicvoiddeleteAll()/*清空整个链表*/{pHead=null;pTail=null;pPointer=null;pLength=0;}publicvoidreset()/*链表复位，使第一个结点成为当前结点*/{pPointer=null;}publicbooleanisEmpty()/*判断链表是否为空*/{return(pLength==0);}publicbooleanisEnd()/*判断当前结点是否为最后一个结点*/{if(pLength==0)thrownewjava.lang.NullPointerException();returntrue;return(cursor()==pTail);}publicPreRelcurrentNode()/*返回当前结点的值*/{PreReltemp=cursor();returntemp;}publicvoidinsert(PreRele){if(pLength==0){pTail=e;pHead=e;}{PreReltemp=cursor();e.pNext=temp;if(pPointer==null)pHead=e;pPointer.pNext=e;}pLength++;}/*返回链表的大小*/{}publicPreRelremove()/*将当前结点移出链表，下一个结点成为当前结点，假如移出的结点是最后一个结点，则第一个结点成为当前结点*/{PreReltemp;if(pLength==0)thrownewjava.util.NoSuchElementException();{temp=pHead;deleteAll();}{PreRelcur=cursor();temp=cur;if(cur==pHead)pHead=cur.pNext;{pPointer.pNext=null;pTail=pPointer;reset();}pPointer.pNext=cur.pNext;pLength--;}returntemp;}publicPreRelcursor()/*返回当前结点的指针*/{if(pHead==null)thrownewjava.lang.NullPointerException();elseif(pPointer==null)returnpHead;returnpPointer.pNext;}}classPreRel//构成链表的结点定义{Stringdestination;Stringtarget;PreRelpNext;PreRel(Strings,Stringd,Stringt)//构造函数{destination=d;target=t;pNext=null;}}publicclassTrans{publicstaticvoidmain(String[]args){Lista=newList();//创建链表，用来存放所有规则Stringrules[]=newString[5];//存放规则的String型数组rules[0]="iptables-AINPUT-s87-d-jREJECT";//输入规则rules[1]="iptables-AINPUT-s/16-d-jREJECT";rules[2]="iptables-AINPUT-s64-d-jACCEPT";rules[3]="iptables-AINPUT-s/24-d-jACCEPT";rules[4]="iptables-AINPUT-s/24-d-jACCEPT";for(inti=0;i<5;i++)//对规则进行形式化{Stringe=rules[i];Transtrans=newTrans();//创建Trans类的对象if(a.head==null){Noden=trans.parse_rule(e);a.insert(n);}{Noden=trans.parse_rule(e,a.length,a);//规则形式化a.insert(n);//将结点插入}}Nodecur_n=a.head;//当前结点为头结点for(inti=0;i<a.length;i++)//寻找每一条规则的前相关集{System.out.print(cur_n.source+"");System.out.print(cur_n.destination+"");System.out.println(cur_n.target);if(cur_n.preRel==null){System.out.println("无前相关集");}elseif(cur_n.preRel.pLength!=0){PreRelcur_p=cur_n.preRel.pHead;//当前相关结点为当前结点的前相关集的头结点for(intj=0;j<cur_n.preRel.pLength;j++)//输出每一条前相关规则{System.out.print(cur_p.source+"");System.out.print(cur_p.destination+"");System.out.println(cur_p.target);cur_p=cur_n.preRel.cursor().pNext;//前相关集链表的指针后移}}elseSystem.out.println("无前相关集");cur_n=cur_n.next;//链表指针后移System.out.println();}}publicNodeparse_rule(Stringe,intl,Lista)//对规则进行形式化，以结点类型返回{Stringr=e;Stringsub[]=r.split("-");//截取“-”符号之间的子字符串Strings=sub[2].substring(sub[2].indexOf("")+1,sub[2].length());Stringd=sub[3].substring(sub[3].indexOf("")+1,sub[3].length());Stringt=sub[4].substring(sub[4].indexOf("")+1,sub[4].length());ListPpr=prerel(s,d,l,a);//存储前相关集Noden=newNode(s,d,t,pr);//创建结点对象returnn;//返回该结点}publicNodeparse_rule(Stringe)//只有当链表为空时调用该函数对对规则进行形式化{Stringr=e;Stringsub[]=r.split("-");//截取“-”符号之间的子字符串Strings=sub[2].substring(sub[2].indexOf("")+1,sub[2].length());Stringd=sub[3].substring(sub[3].indexOf("")+1,sub[3].length());Stringt=sub[4].substring(sub[4].indexOf("")+1,sub[4].length());ListPpr=null;//前相关集为空Noden=newNode(s,d,t,pr);returnn;}publicListPprerel(Strings,Stringd,intlength,Lista)//求规则的前相关集，以链表类型返回{ListPLP=newListP();//创建前相关集的链表对象if(length!=0){Listl=newList();//创建结点的链表l.reset();//使第一个结点成为当前结点Nodecur_n=l.cursor();//返回当前结点的指针if(length==1)//当链表长度为1时{if(is_relate(cur_n,s,d))//判断是否相关{PreRelp=newPreRel(cur_n.source,cur_n.destination,cur_n.target);LP.insert(p);//判断是否相关}}{for(inti=0;i<length;i++){if(is_relate(cur_n,s,d))//判断是否相关{PreReltmpn=newPreRel(cur_n.source,cur_n.destination,cur_n.target);LP.insert(tmpn);//判断是否相关}cur_n=cur_n.next;//链表指针后移}}}returnLP;}publicbooleanis_relate(Noden1,Stringsource,Stringdestination)//判断两条规则是否相关，{double[]pre_s=newdouble[2];double[]pre_d=newdouble[2];double[]new_s=newdouble[2];double[]new_d=newdouble[2];pre_s=ip_range(n1.source);//存放源地址的范围pre_d=ip_range(n1.destination);//存放目的地址的范围new_s=ip_range(source);new_d=ip_range(destination);booleanflags=false;booleanflagd=false;if(pre_s[0]<new_s[0]){if(new_s[0]<=pre_s[1]){flags=true;}elseflags=false;}if(pre_s[0]<=new_s[1]){flags=true;}elseflags=false;}if(pre_d[0]<new_d[0]){if(new_d[0]<=pre_d[1]){flagd=true;}elseflagd=false;}if(pre_d[0]<=new_d[1]){flagd=true;}elseflagd=false;}if(flags&&flagd){returntrue;}elsereturnfalse;}publicdouble[]ip_rang