HTTPS 与互联网可信、安全连接机制概貌

由于互联网开放的特性,在网络中传送的信息十分容易在途中各个环节上被他人截获、窃取和篡改,这威胁到了在网络中传输的敏感数据的安全。HTTP 是目前互联网中应用最广泛的应用层协议,所有基于 Web 的应用和多数移动 App 都通过 HTTP 与服务器通信。之前的文章HTTP 协议概貌中提到,HTTP 是一个基于 TCP 的应用层协议,HTTP 传送的所有信息,包括 HTTP 头部在内都是不作任何处理直接交付给 TCP 来传输的,敏感信息在这个过程中可能被泄露,也可能被篡改而损害通信双方的利益。例如用户在通过输入用户名和密码登录一个 Web 站点时,浏览器向服务器提交的用户名和密码就可能被他人截获;在随后的正常浏览过程中,HTTP 头部中用于维持会话的 cookie 也可能被他人截获,直接威胁用户账号的安全。

为了解决 HTTP 传输数据安全的问题,网景公司最早在 1994 年推出了 HTTPS 协议。HTTPS 协议不直接使用 TCP 传送 HTTP 的数据流,而是在原有的 HTTP 与 TCP 之间加入了一层安全套接层(Secure Sockets Layer,SSL),浏览器与服务器双方都将 HTTP 的数据流先用非对称加密算法加密之后再交付给 TCP,双方的 SSL 收到数据后再通过相应的密钥将数据先解密,再交付给 HTTP 层解析。HTTPS 在互联网中传送的都是不能直接理解的密文,即使在传输过程中被他人截获,攻击者也几乎没有办法将截获的密文复原成原文,这样保证数据在传输过程中的安全。

对于互联网中 Web 站点的用户来说,除了信息在传输过程中可能被窃取之外,还有另一个潜在的安全威胁,那就是仿冒网站的问题。几乎所有的 Web 站点都是通过域名来访问的,如果攻击者通过 DNS 欺骗等手段将浏览器请求的域名解析到一个仿冒网站上,用户在不知情的情况下可能会向仿冒网站主动提交用户名密码等敏感信息。对于仿冒网站的问题,HTTPS 也有数字签名、数字证书等机制防止这种攻击发生,下文将讨论它们的原理。

互联网上对信息安全极为敏感的服务如网上银行等很早就使用 HTTPS 来保障传输数据的安全,许多其他大型网站为了安全,也在登录页上使用 HTTPS 保护用户的用户名和密码等。近期,国内外越来越多知名网站已经开始全站从 HTTP 升级到 HTTPS,HTTPS 化已经成为未来互联网的发展趋势。

1. SSL 与 TLS

SSL 最早是网景公司为了保证 HTTP 安全而设计的安全套接层,SSL 对上层的 HTTP 来说是透明的,因此也能在 SSL 上运行其他的应用层协议来给其他应用提供同样的安全保障。随后 IEFT 将 SSL 标准化,将其更名为传输层安全协议(Transport Layer Security,TLS),并于 1999 年公布了第一版 TLS 标准文件。后又公布了 RFC 5246(2008年8月)和 RFC 6176(2011年3月)。浏览器、电子邮件、即时通讯、VoIP 和网络传真等应用程序都广泛支持 TLS 协议[1]

SSL/TLS 的设计目标是通过一个不安全的网络通道在两个应用程序之间建立安全的连接,防止传输的信息被窃取和篡改。TLS 通过非对称密钥加密建立安全连接来协商和交换下一步对称加密用的算法和密钥,并在公钥基础设施(Public Key Infrastructure,PKI)的参与下通过数字证书实现可信的身份认证。关于非对称加密算法、数字证书和 PKI 等概念还将在下文中继续讨论。

TLS 连接的建立大致分为协商阶段、交换密钥和证书阶段以及基于对称密钥加密的保密传输阶段等。

1.1 协商阶段

建立 TLS 连接第一步就是客户端与服务端双方通过握手消息交换相互支持的协议版本、加密算法和压缩算法等信息,通过协商一致使用一种双方都支持的连接参数。在这个过程中,客户端先向服务端发送一个 ClientHello 消息,其中包含客户端所支持的 TLS 协议版本、密码套件列表、压缩方式、一个用于生成会话密钥的随机数以及扩展的其他信息(例如服务器名称、上层协议)等。下图展示了一个 TLS 连接建立过程中客户端向服务端发送的 ClientHello 消息的分析结果。

tls-client-hello图 1 对一个 TLS 连接阶段 ClientHello 消息的分析

服务端收到 ClientHello 后,根据自身的情况选择一组双方都支持的、最合适的参数,通过 ServerHello 确认给客户端,同样也会发送一个用于生成会话密钥的随机数。下图是对上述 TLS 连接过程中服务端响应给客户端的 ServerHello 的分析结果。

tls-server-hello图 2 对上述 TLS 连接阶段 ServerHello 消息的分析

1.2 交换证书和公钥阶段

进行一轮 ClientHello / ServerHello 握手之后,服务端会通过 Certificate 消息向客户端发送一个证书以证明自己的身份,同时证书里还包含一份公钥。如果双方协定 Diffie-Hellman 算法交换会话密钥,此时服务端还会发送一个 ServerKeyExchange 握手消息。如果采用的是双向认证方式,此时服务端还会发送 CertificateRequest 消息,请求客户端提供证书。最后服务端发送 ServerHelloDone 消息表示服务端结束握手消息。

客户端收到 ServerHelloDone 之后,如有必要,先通过 Certificate 消息发送自己的证书。随后通过 ClientKeyExchange 消息发送密钥。需要注意的是如果双方协定采用 Diffie-Hellman 算法交换会话密钥,此时这时传送的是未加密的客户端 DH Key;如果采用 RSA 交换密钥,此时传送的是经过服务端公钥加密的会话密钥。

接着客户端发送 ChangeCipherSpec 消息,这是客户端发出的最后一个明文消息,意味着从此客户端发出的数据均是经过会话密钥加密的信息。随后客户端发送第一个加密的消息:Finished。

服务端收到 Finished 之后,同样发送最后一个明文消息:ChangeCipherSpec,接着同样发送加密的 Finished。此时 TLS 最后一次握手完成,双方都通过加密的方式传送应用层数据,TLS 连接进入保密传输阶段。

1.3 保密传输阶段

这个阶段双方发送的消息均为 ApplicationData,其中运载的应用层数据是通过会话密钥加密的。

下面是从 RFC 5246[2] 中摘录的 TLS 连接握手的完整时序。

      Client                                               Server

      ClientHello                  -------->
                                                      ServerHello
                                                     Certificate*
                                               ServerKeyExchange*
                                              CertificateRequest*
                                  <--------       ServerHelloDone 
      Certificate*
      ClientKeyExchange 
      CertificateVerify* 
      [ChangeCipherSpec]
      Finished                    -------->
                                               [ChangeCipherSpec]
                                  <--------              Finished
      Application Data            <------->      Application Data

   * Indicates optional or situation-dependent messages that are not
   always sent.

2. 加密

在密码学中,加密是指将信息通过某种方式编码,使之只能被有授权的人读取。加密本身并不能阻止信息被截获,但加密过的信息内容对于攻击者来说是无意义的,只有相应密钥的持有者才能将加密过的信息还原成明文信息,这个过程称为解密。密钥是在加密算法中用于加密和解密的参数,通常是一个大的整数。有些加密算法使用同一个密钥加密和解密信息,另一些则使用不同的密钥,前者称为对称加密算法,后者称为公钥加密算法(或非对称加密算法)。这两种加密算法都在 TLS 中有应用。

2.1 对称加密算法

在前文提到的 TLS 连接中,在保密传输阶段 TLS 携带的应用层数据就是用一个会话密钥进行对称加密过的。对称加密又称为共享密钥加密,对称加密的密钥既能用于加密也能用于将密文解密成原文;在对称加密中,加密方和解密方共同使用同一个密钥进行加密和解密操作。常见的对称加密算法有 DES、3DES、AES、IDEA、RC5、RC6 等。

对称加密算法要求通信双方都拥有同一个密钥,并且密钥不能被第三者知道,因此双方如何安全地协商并交换密钥是一个需要解决的问题。Diffie-Hellman 是第一个实用的在非保护信道中建立共享信道的方法[3]。它的基本原理是通信双方各自生成一个随机数,然后通过一些运算将双方的随机数转换为两个公钥,并在非保护的通信信道中交换这两个公钥,然后双方都可以根据对方的公钥及自己的随机数计算出一个相同的公共密钥。并且这个算法保证了即使攻击者窃取了通信过程中交换的两个公钥,也极难计算出用于对称加密的公共密钥。本文不准备讨论 Diffie-Hellman 算法的具体数学原理,如有兴趣,可以参考维基百科 Diffie-Hellman 词条,这里有这个算法包括数学原理在内的更详细的细节。

另外,还可以先通过 RSA 等公钥加密机制来交换双方的共享密钥。TLS 支持用 Diffie-Hellman 算法交换共享密钥也支持用公钥加密机制交换共享密钥。

2.2 公钥加密算法

公钥加密算法也称为非对称加密算法,它的特征是一次生成一对密钥,一个只能用于加密,另一个只能用于解密,并且已知其中一个密钥无法推导出另一个密钥。在应用中,在非保护信道中公开将两个密钥的其中一个传送给对方,另一个自己保留。公开的那个密钥称为公钥,保留的密钥称为私钥。

当公开的是加密密钥时,这个算法可以用于建立单向的保密通信通道:收信者生成一对密钥,将加密密钥当作公钥发送给对方,对方用公钥加密信息,收信者用秘密的私钥解密得到原文。在这个过程中即使攻击者截获了用公钥加密的信息,但没有私钥就无法解密这些信息,信息的安全得到了保证。

当公开的是解密密钥时,加密密钥的持有者可以用手中的加密密钥对信息进行数字签名,公钥(解密密钥)的持有者可以通过解密对收到的信息进行确认,这样可以保障信息在传输过程中不受篡改和伪造,并确认信息发送者的身份。

公钥加密算法的上述两种应用场合都在 TLS 协议中有运用。同时,公钥加密算法还是数字证书机制的基础。最常见的一种公钥加密算法是 RSA 算法,维基百科 RSA 算法词条中有这种算法的详细数学原理。

3. 数字证书:数字身份认证机制

回顾前文中讨论的 TLS 连接建立过程,试想如果一个 TLS 连接使用 Diffie-Hellman 交换会话密钥,而在连接的交换密钥阶段服务端发送的 ServerKeyExchange 被一个第三方的攻击者劫持,这个攻击者再伪装成服务器向客户端发送它自己的 ServerKeyExchange,另一方面又伪装成客户端欺骗真正的服务器,这样一来似乎就构成了一次中间人攻击,攻击者可以在服务器和客户端之间伪装对方,窃取通信的信息。

然而上述的情形是不会发生的,TLS 具有身份认证的机制来防范中间人攻击。

3.1 数字签名

前文已经提到,在公钥加密算法中,如果公开解密密钥,那么信息发送者可以用加密密钥进行数字签名,接收者使用公钥进行确认,防止信息在传输过程中被伪造和篡改。在一份记载有文字信息的纸质文件上进行签名或者签章,代表签名者认可文件中所记载的内容,他人伪造的没有签名的文件和有修改痕迹的签名文件都会被认为是无效的。数字签名也是如此,一份附带有数字签名的电子信息文件,表示签名者认可这份电子信息的内容,并通过公开密钥加密算法保证这份文件无法伪造和被篡改,其他人都可以通过公钥来验证这份电子信息的真伪。

要进行数字签名,首先需要选定一种信息摘要算法。信息摘要算法是一种将任意长的信息不可逆地转换成较短的固定长度的信息的算法,常见的有 MD5、SHA-1、SHA-256 等算法。使用选定的信息摘要算法对要签名的文件计算一个摘要,然后用自己的私钥加密这个信息摘要,加密的结果就是对这份文件的数字签名。其他人收到这份文件后,先用相同的信息摘要算法对文件的正文求信息摘要,然后再用相应的公钥解密数字签名,将解密的结果与求得的信息摘要进行比对,如果两者一致则说明校验成功,这份文件是可信的;否则校验失败,说明这份文件可能是伪造的或者被篡改过的。

使用 Diffie-Hellman 交换会话密钥的 TLS 连接在交换密钥阶段,正是用数字签名的技术来防范中间人攻击的。在 1.2 节中提到在交换密钥阶段,服务端会先通过 Certificate 握手消息向客户端发送一个数字证书,数字证书中包含有一个公钥。在其后的 ServerKeyExchange 消息中,除了有交换的密钥信息之外,还有一个数字签名,客户端收到这个消息之后,使用服务端证书中的公钥来验证 ServerKeyExchange 消息是否可信。下面的图片展示了一个 ServerKeyExchange 消息的分析,可以看到其中有数字签名使用的算法、数字签名的长度和数字签名等几个字段。

tls-server-key-exchange图 3 TLS 连接过程中的一个 ServerKeyExchange 消息

3.2 数字证书与 PKI

在 3.1 小节中提到了服务端会向客户端发送一个 Certificate 消息,其中包含了一个数字证书,数字证书中有服务端的公钥。再考虑一下中间人攻击的手段,攻击者会不会先向客户端发送自己的证书,然后用自己的私钥签名 ServerKeyExchange 来欺骗客户端呢?答案是不行。数字证书之所以称为证书,是因为它是无法伪造的,攻击者如果自己发送一个假证书给客户端,客户端效验的时候就会发现它是伪造的,伪造的数字证书不会被信任。

数字证书无法伪造,是因为数字证书上有一个由数字证书认证机构(Certificate Authority,CA)签署的数字签名。数字证书上记载有服务器的域名和其他与服务器的身份相关的信息,以及一个验证数字签名用的公钥。当服务器管理员要为服务器申请一个数字证书时,必须将上述的材料提交给权威的数字证书认证机构审核,审核通过后会将申请中提交的信息填入数字证书,并用自己的私钥签上数字签名,表明该机构已核实证书中记载的全部信息。

CA 用于签发数字证书的私钥也对应一张证书,这张证书中的公钥用于验证该 CA 签发的数字证书的真伪。那么,CA 的数字证书又是由谁签发的呢?答案是由另一家更权威的机构签发的。这样,数字证书一级一级构成一个信任链,信任链的顶端就是根证书。根证书不由其他机构签发,它通常是通过预装在操作系统的“受信任的根证书存储区”中自动受到信任,根证书的私钥由相应的权威机构保管和控制。

上述的由软件、硬件、管理政策和机构组成的数字信任体系称为公钥基础设施(Public Key Infrastructure,PKI),建设公钥基础设施的目的在于创造、使用、管理、分配、存储和吊销数字证书[4]

3.3 数字证书的吊销机制

数字证书使用者必须妥善保管好用于签名的私钥,如果私钥被其他人盗取,攻击者就可以用盗来的私钥签署数字签名,冒充真正的数字证书持有者,这时候数字证书就失去了它应有的作用。好在 CA 签发的数字证书还有吊销的机制。CA 签发的数字证书中含有一个数字证书吊销列表(Certificate Revocation List,CRL)字段,该字段指向一个网络上的数字证书吊销列表,由证书的颁发者负责维护。当证书使用者发现自己的私钥可能被窃取时,就可以通知 CA 将该证书的序列号加入到证书吊销列表中。软件验证证书的时候也会检索证书吊销列表,如果发现证书的序列号在吊销列表中,则会认为该证书不可信。

但是根证书没有证书吊销列表也没有吊销机制,如果根证书的私钥发生泄密,则是非常严重的事故,攻击者可以利用窃取的根证书私钥签发假证书,将会危及整个体系的安全。历史上发生过 CA 泄露私钥的事故,处置危机的方案是各操作系统、浏览器等软件厂商发布补丁,把该 CA 的根证书从受信任的根证书列表中移除。另外历史上还有国内某家 CA 机构滥发假证书,事情败露后被各大操作系统和浏览器厂商从信任列表移除根证书的事件

参考文献
[1] Wikipedia. 传输层安全协议. https://zh.wikipedia.org/wiki/%E5%82%B3%E8%BC%B8%E5%B1%A4%E5%AE%89%E5%85%A8%E5%8D%94%E8%AD%B0
[2] T. Dierks, E. Rescorla, et al. The Transport Layer Security (TLS) Protocol Version 1.2, RFC 5246, Aug 2008; tools.ietf.org/html/rfc5246
[3] Wikipedia. 迪菲-赫爾曼密鑰交換. https://zh.wikipedia.org/wiki/%E8%BF%AA%E8%8F%B2-%E8%B5%AB%E7%88%BE%E6%9B%BC%E5%AF%86%E9%91%B0%E4%BA%A4%E6%8F%9B
[4] Wikipedia. 公開金鑰基礎建設. https://zh.wikipedia.org/wiki/%E5%85%AC%E9%96%8B%E9%87%91%E9%91%B0%E5%9F%BA%E7%A4%8E%E5%BB%BA%E8%A8%AD

要救的不只有民科,还有看客们

一段五年前的综艺节目视频突然被翻了出来,冠以“他综艺首提引力波竟遭方舟子残酷打压”的标题在网络上传得大红大紫。我看了一遍视频,觉得好笑;又翻看了众多网友的评论,不禁感到遗憾、失落、愤懑。想在评论里振臂疾呼:民科要不得!又有一种声音淹没在人海里的无力感。冷静一下,写点浅薄的文字,权当发泄情绪和安慰自己。

视频里的主角是一位初中学历、50 多岁的民间科学家。这位言必称诺贝尔物理学奖的“科学家”声称发现和开创了“统一物理学”,把“引力波”、“物质波”等新鲜的科学名词杂糅进一个不知所云的“理论”,肤浅地臆想出“汽车不用轮”、“活神仙”等“技术”实用方向。

我想一个具备基本科学素养的人看了他的表演就会对其嗤之以鼻。节目里的主持人和各路嘉宾显然也不为他的新发现所动,对这位有拿诺贝尔奖的雄心壮志的民科极尽嘲讽之事。五年前主持人的嘉宾们在电视节目上公开对他发动嘲讽攻击也许确有些不妥,但这位民科的遭遇不值得同情,更不值得喝彩。

民间科学家是对极少接受过(甚至拒绝)正规科技学习及训练,理论知识及学术素养匮乏,却又经常热衷于相关领域研究之人士的一种称谓,通常具有讥刺贬义[1]。他们的“研究”不建立正统科学体系之上,甚至违背最基本的科学定律,却往往借用各种科学名词来使他们的“成果”看上去很科学。民科常常活跃在数学和物理学等学科,数论、相对论、量子力学等领域是最热门的研究方向,哥德巴赫猜想的证明、永动机的实现等是最常见的“研究成果”。

民科做出来的“研究”不被正统的科学界承认,便拿哥白尼、爱因斯坦等先驱“类似的事迹”来麻痹自己,做出一副受了科学迫害的姿态,宣称迟早有一天他的成果会得到广泛的认可,最终拿诺奖、迎娶白富美,走上人生巅峰。对待为了所谓的科学研究而走向偏执和狂妄深渊的人,就应如节目中董浩多次强调的:救人要紧

然而五年前一个民科被各路人士嘲讽的节目视频在引力波的存在被实验证实之后突然又火了起来,人们声称:他是对的,你们欠他一个道歉。仿佛这位当代哥白尼蒙冤多年,证人清白的时刻终于来了。

如果看客们稍有一点科学素养,稍有一点置疑求证的精神,就能在查阅资料之后发现引力波其实是相对论的一部分,是爱因斯坦最早提出来的,这位郭先生不过是拾人牙慧拿了个你们听不懂的名词装裱他的伪科学而已。

还有一些看客大打起感情牌,声称他是一位只有初中学历的下岗职工,做的研究好不好没关系,精神可嘉,应该支持他。这种持有他弱他有理逻辑的人不是圣母,是反智主义的帮凶。有了你们的支持,不仅让郭先生在民科深渊中越陷越深,更会让千千万万没有接受过正规科学基础教育而又抱有拯救世界远大妄想的人走上民科的道路。

缺乏基本科学素养的看客们在网上声援一个不学无术的民间科学家,而在面对真正的现代科学技术时,却又是一副反科学的嘴脸。他们反通信基站、反核电、反现代医学、反化学工业、反生物工程、反转基因,不辨是非。

救人要紧。不只是对民科说的,更是对围观者们说的。我们需要开展自救,多阅读,多学习,多思考。建立基本的科学素养,以明是非。

参考文献
[1] Wikipedia. 民间科学家. https://zh.wikipedia.org/wiki/%E6%B0%91%E9%97%B4%E7%A7%91%E5%AD%A6%E5%AE%B6

NAT:网络地址转换

之前的文章IP 与路由(一)中提到当前日益突显的 IPv4 地址耗尽问题,NAT 技术的广泛运用一定程度上缓解了该问题。NAT 是一种通过修改 IP 数据报头部信息来将一个 IP 地址空间映射到另一个 IP 地址空间的技术,这种映射操作通常由网络中的防火墙完成,包括硬件防火墙和软件防火墙。

NAT 的一个最广泛的应用场合是将一个局域网接入 Internet。在一个局域网中,通常每台主机都配置有私网地址,局域网中的各主机通过私网 IP 地址相互通讯。当局域网中的主机有访问 Internet 的需求时,需要先向 ISP 申请公网 IP 地址,再通过 NAT 设备将局域网中所有发往 Internet 的流量的源地址转换成这个公网 IP 地址。NAT 设备还会为局域网中所有主机与 Internet 的连接维护一个会话,保证从 Internet 返回的 IP 分组能正确地转发到局域网中对应的主机上。日常所见的家庭小型网络往往属于上述接入方式。

运用 NAT 技术可以达到使局域网中多台主机共享一个公网 IP 地址的目的,节约了 IP 地址。另一方面,NAT 向 Internet 隐藏了 NAT 背后局域网的地址空间、网络结构等细节;同时,由于 NAT 的存在,来自 Internet 的请求不能直接到达局域网,这使局域网中的主机免受来自 Internet 的探测、攻击和入侵。

基本 NAT

基本 NAT 是一种最简单的 NAT 形式。基本 NAT 配置有多个外网 IP 地址,在出站时,每个内网 IP 地址都会动态分配并映射到一个独立的外网 IP 地址。也就是说,基本 NAT 是一种只映射 IP 地址的 NAT,因此这种 NAT 又称为一对一 NAT。基本 NAT 需要维护一个会话表,将内网的 IP 地址与会话分配的外网 IP 地址一一对应起来。

在一个内网 IP 数据报穿过基本 NAT 去往外网时,NAT 会根据映射将这个 IP 数据报中的源 IP 地址字段修改为它对应的外网 IP 地址,并调整 IP 地址头部的校验和字段以及上层协议(TCP、UDP 等)中的校验和字段,然后将其交付给路由器。当基本 NAT 收到一个来自外网的 IP 数据报时,会将这个数据报头部中的目标 IP 地址字段修改为映射中对应的内网 IP 地址,同样调整校验和之后将数据报发往内网。

基本 NAT 只转换 IP 地址,不转换上层协议中的端口号等字段。

一对多 NAT

基本 NAT 只是简单地转换 IP 数据报中的 IP 地址,并不能起到复用外网 IP 地址的作用。当只从 ISP 处分配到一个外网 IP 地址,而内网中又有多台主机需要接入外网时,就需要使用一对多 NAT。一对多 NAT 通过转换上层协议的端口号来达到复用外网 IP 地址的目的,这种 NAT 方式也称为网络地址端口转换(Network Address Port Translation, NAPT)。日常所见的家庭小型网络等就是通过这种方式接入互联网的。

常见的运输层协议——例如 TCP 和 UDP 等——的数据报头部都有源端口号和目标端口号等字段,端口号用于区分同一台主机上不同的服务、进程等。NAPT 利用这一点,同时修改出站 IP 数据报头部中的源 IP 地址和上层协议的源端口号,为每一个出站会话动态分配一个未占用的端口号,并建立映射。NAPT 也需要维护一个会话表,将内网 IP 地址、上层协议号、上层协议源端口等与外网 IP 地址、上层协议号、外网上层协议端口等信息一一对应。

在一个内网 IP 数据报穿过 NAPT 运往外网时,NAPT 先在映射表中检查是否有与该 IP 数据报的源 IP 地址、上层协议号和上层协议端口号完全匹配的项目,如果有,则将它 IP 头部的 IP 地址信息修改为外网 IP 地址,将上层协议的端口号修改为映射表中记载的端口号;如果映射表中没有匹配的项目,那么先分配一个暂未使用的端口号,并写入映射表,然后再修改 IP 数据报头部的 IP 地址及上层协议的端口号。与基本 NAT 一样,在修改了这些字段之后还需要视情况调整 IP 数据报头部及上层协议头部的校验和字段。做完这些处理后,IP 数据报将被交付给路由器。

当 NAPT 收到来自外网的 IP 数据报时,通常需要根据 IP 数据报的目的 IP 地址、上层协议号和目的端口号等信息反向查询映射表,对 IP 数据报的 IP 地址等字段进行相应的转换然后发往内网。来自外网不匹配映射表的 IP 数据报将会被丢弃处理。

下图展示了一个典型的通过 NAPT 接入 Internet 的局域网。

napt图 1 一个通过 NAPT 接入 Internet 的局域网

NAPT 的映射表将内网的地址-端口与地址转换后对应的外网地址-端口建立了一种联系,并根据这种联系将外网主机返回的 IP 数据报转发给内网的主机。在实践中,有几种不同的 NAT 实现对来自外网的 IP 数据报的检查方式略有不同,这最终表现在对来自外网的 IP 数据报的处理行为有所不同,下文将详细讨论这几种情况。

 NAT 的几种过滤行为

以 UDP 数据报为例,当一个内网端点通过 NAT 建立一个出站会话时,NAT 会在内网地址-内网端口(记作 X:x)与目标的地址-端口(记作 Y:y)的映射之间指派一些过滤规则[1]。这意味着可能并不是所有来自外网的数据报都能被 NAT 映射到内网,其中有一些可能会被过滤掉。

1. 端点无关过滤

这种 NAT 只检查来自外网的数据报中的目标地址和端口,将无法在映射表中找到对应的内网地址-端口的数据报过滤掉,而不管这个数据报的源地址 Z 和源端口 z(记作 Z:z)是什么。这意味着这种 NAT 会将任何来自外网且能找到映射关系的数据报进行相应的转换并送往内网。

2. 地址相关过滤

同样,这种 NAT 也会将无法在映射表中找到对应内网地址-端口的数据报过滤掉。另外,这种 NAT 还会检查来自外网的数据报的源地址 Z,如果映射表中对应的主机 X:x 之前从未向 Z 发送过任何数据报,这个数据报也会被过滤掉。也就是说,一个来自外网 Z:any 的数据报能被 NAT 转换并发往 X:x 的条件是 X:x 曾经向 Z 主机的任一端口发送过数据报。

3. 地址端口相关过滤

这种 NAT 的过滤规则更加严格。除了不能在映射表中找到对应关系的数据报会被过滤之外,NAT 还会同时检查来自外网的数据报的源地址 Z 和源端口 z(Z:z),只要映射表中对应的主机 X:x 从未向 Z:z 发送过任何数据报,这个数据报就会被过滤掉。这种 NAT 的过滤执行的是最严格的检查,只有会话建立时内网主机指定的目标地址和端口发出的响应才能被转换并送回内网。

ICMP 报文的处理

ICMP 在网络测试、网络差错消息通知等方面有重要的应用,NAT 也应当支持 ICMP 报文。TCP、UDP 等运输层协议的头部中都有端口(Port)字段,可以在 NAPT 中发挥作用。而 ICMP 作为基于 IP 的网络层协议,它的头部中并没有端口字段,因此 NAT 对 ICMP 报文的处理略有不同于 TCP 和 UDP。

1. ICMP Echo Reply 报文

ICMP Echo Reply 应用于 Ping 程序。当在内网中向外网的主机应用 Ping 程序的时候,内网发出的 ICMP Echo 报文会穿过 NAT 送往外网主机,外网主机响应的 ICMP Reply 报文需要穿过 NAT 送达对应的发送者。

尽管 ICMP 不像 TCP、UDP 等协议一样头部中有端口号字段,但 ICMP Echo Reply 的消息中有一个 Identification 字段,这个字段的作用类似于 TCP/UDP 的端口号,用于区分同一个主机上正在运行着的不同 Ping 会话。因此,在对 ICMP Echo Reply 报文进行 NAT 处理时,可以直接将报文中的 Identification 字段当作端口号处理,为每个 NAT 会话分配一个新的 Identification——就像对待 TCP/UDP 的端口号一样——然后转换 IP 地址和 Identification,将转换过的报文送向外网。当 NAT 收到来自外网的 ICMP Reply 时,根据报文中的目的 IP 地址和 Identification 在映射表中查找对应的内网主机信息,然后完成相应的地址转换送往内网。

2. ICMP 差错报文

当一个 IP 报文在网络中发生了某些差错(如目标不可达、TTL 超时、分片问题等)时,处理该报文的主机会向发送者递交一个 ICMP 差错报文以通知发送者,这个从外网传回的差错通知报文也必须能通过 NAT 并正确地送达对应的内网主机。

与 ICMP Echo Reply 不同,ICMP 差错报文是由外网主机先发起的,而且这种报文中也没有 Identification 之类的信息,因此无法像对 ICMP Echo Reply 一样处理 ICMP 差错报文。好在 ICMP 差错报文会在数据区将出差错的 IP 数据报的头部以及首 8 字节的 data 载荷传送回来,NAT 在收到这种报文时可以将出差错的原始数据报头部的协议号、源地址和源端口号取出来,并在映射表中查询,找到对应的内网主机记录后完成转换和发送。

其他话题

一方面 NAT 技术的运用对外隐藏内网的细节,隔绝了来自外网访问和连接,在 NAT 的保护下的内网主机比直接暴露在外网的主机更安全;另一方面这种特性也使内网的主机不能直接对外提供服务,并对 P2P 应用造成了很大的影响,基于 P2P 的程序无法直接在两台内网主机之间建立连接。在 NAT 技术广泛运用的背景下,发展出了针对 NAT 环境下 P2P 程序之间建立连接的 NAT 穿透技术。NAT 穿透技术通常是在一台处于外网的第三方服务器的帮助下,巧妙地使一对 NAT 背后的主机穿透 NAT 相互建立连接。有关 NAT 穿透技术的话题将在后续文章中详细讨论。

如需转载本文,请注明出处。

参考文献
[1] F. Audet Ed., Nortel Networks, et al. Network Address Translation (NAT) Behavioral Requirements for Unicast UDP, RFC 4787, Jan 2007; tools.ietf.org/html/rfc4787
[2] P. Srisuresh, Kazeon Systems, et al. NAT Behavioral Requirements for ICMP, RFC 5508, Apr 2009; tools.ietf.org/html/rfc5508
[3] P. Srisuresh, M. Holdrege, et al. IP Network Address Translator (NAT) Terminology and Considerations, RFC 2663, Aug 1999; tools.ietf.org/html/rfc2663
[4] P. Srisuresh, Jasmine Networks, et al. Traditional IP Network Address Translator (Traditional NAT), RFC 3022, Jan 2001; tools.ietf.org/html/rfc3022
[5] Wikipedia. Network address translation. https://en.wikipedia.org/wiki/Network_address_translation

IP 与路由(二)

IP 使用 IP 数据报运送上层协议的交付的数据到目标主机,IP 数据报由 IP 头部和数据载荷两部分组成。

IP 头部

IP 头部位于每个 IP 数据报的起始位置,IP 头部中包含 IP 数据报的版本、源 IP 地址、目的 IP 地址、TTL 等重要信息。IPv4 与 IPv6 的头部结构有所不同,如无特殊说明,本文中所讨论的 IP 头部均指 IPv4 的头部。IP 头部中一共有 14 个字段,其中前 13 个字段是必选的。一个 IP 头部的结构如下所示[1]

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |Version|  IHL  |    DSCP   |ECN|          Total Length         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |         Identification        |Flags|      Fragment Offset    |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  Time to Live |    Protocol   |         Header Checksum       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                       Source Address                          |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                    Destination Address                        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                    Options                    |    Padding    |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Version

IP 头部最起始部分的 4 bits 是 Version 字段,这个字段与 IPv6 头部兼容,用于标识数据报的版本号。对于 IPv4 的数据报来说,这个字段的值为 4。

IHL

IHL 字段表示 IP 数据报头部的长度(Internet Header Length),是一个 4 bits 长的字段。IP 数据报是按 32 bits(4 字节)对齐的,它的位长度一定是 32 的整数倍,IHL 的值表示的是 IP 数据报长度对 32 bits 的倍数。例如,假设一个 IP 数据报的 IHL 字段值是 6,则说明这个数据报 IP 头部的长度是 6 x 32 bits = 192 bits(24 字节)。IP 数据报头部的长度不会短于 160 bits(20 字节),因此一个有效的 IHL 字段值不小于 5。

DSCP

DSCP 字段是一个 6 bits 长的差异化服务代码(Differentiated Services Code Point)。在 Internet 发展的过程中,人们发现互联网中开始同时传送着多种不同类型服务的数据,包括语音、视频、音乐流媒体、网页和电子邮件等[2]。为了保证提供尽量好的服务质量,不同互联网服务本身的一些特性决定了它们的数据报在被转发时应当采取不同的策略——例如网络语音服务对延迟比较敏感,因此它们的数据报需要优先于文件传送服务的数据报被转发。DSCP 字段标志了一个 IP 数据报所属的服务类型,网络设备可以依据这个字段的值提供差异化的转发行为。默认的 DSCP 值是 0。

ECN

ECN 是一个 2 bits 长的字段,用于为 IP 和 TCP 提供显式的拥塞通知,以取代用丢弃数据报的方式控制拥塞。关于 ECN 更详细的信息,请参考 RFC 3168 文档及维基百科 Explicit Congestion Notification 词条。

Total Length

Total Length 是一个 16 bits 长的字段,用于表示整个 IP 数据报的长度,包括头部和数据载荷,单位是字节。由于一个 IP 数据报至少应包含头部,而上文中提到最短的 IP 头部长度是 160 bits,因此 IP 数据报总长度不会小于 160 bits,一个有效的 IP 数据报中 Total Length 字段的值不会小于 20。Total Length 可以表示的最大的数是 216 – 1 = 65,535,因此理论上最大可以有长达 65,535 字节的 IP 数据报。

值得注意的是,尽管 IP 是建立在分组交换链路层上的数据报协议,下层协议也会为 IP 提供明确的边界,但 Total Length 字段的存在是有意义的。这是因为下层协议可能会对每个分组有最短长度的限制或者对对齐方式有特殊的要求,因此在传送 IP 数据报时可能会在原始的数据报末尾增加多余的填充位,此时必须依靠 IP 头部中的 Total Length 来确定数据报的真实长度。例如以太网限制了每一帧的最小长度为 64 字节,除去以太网帧头部的 18 字节之后的数据部分的最小长度是 46 字节。当以太网发送一个总长度小于 46 字节的 IP 数据报时,会在其末尾填充 0 以符合最短 46 字节的要求。

Identification

Identification 字段占 16 bits,是一个唯一标识字段。在一段时间内 IP 每发出的一个数据报都有一个唯一的 Identification,这个字段主要用于标记一组 IP 分片中的每个单独的 IP 数据报以便于接收端重新拼装。

Flags

Flags 字段占 3 bits,是一个标志字段,用于标志 IP 数据报有关分片的信息。这三个标志位的定义分别如下:

  • 第 0 位:保留位,必须置为 0;
  • 第 1 位:DF(Dont’t Fragment),禁止分片位。0 表示允许分片,1 表示不允许分片;
  • 第 2 位:MF(More Fragments),更多分片位。当一个 IP 数据报被分片为多个时,只有最后一个 IP 数据报的 MF 标志为 0,其余的 IP 数据报都将置 MF 标志为 1。

关于 IP 分片的话题,下文中还会有更详细的讨论。

Fragment Offset

Fragment Offset 是一个 13 bits 长的分片偏移字段。该字段用于在分片发生时定位一个分片所携带的数据在原始 IP 数据报的载荷中的偏移,以 8 字节(64 bits)为单位。在未分片的 IP 数据报中,这个字段的值为 0。

Time To Live

Time To Live(TTL)是一个 8 bits 的字段,标识 IP 数据报最多还能在网络中生存多长时间。当一个 IP 数据报在合理的时间内还没有被送到目的主机上时,它可能是经历了错误的路由或进入了环路,此时网络应该丢弃它。在最初的定义(RFC 791)中,TTL 字段的单位是秒,当 IP 数据报被一个模块处理时,应在处理后修改 TTL 字段的值,使其等于原来的值减去这个数据报在处理中消耗的时间(单位秒);RFC 还规定处理时间一律按向上取整计算,例如不足 1 秒的按 1 秒计。

在实践中,由于路由器对 IP 数据报处理的时间通常小于 1 秒,因此实际上路由器对其每个转发的 IP 数据报都是将 TTL 作减 1 处理,最后 TTL 字段变成了按跳数(hops)计的生存时间字段[3]。例如一个 IP 数据报的 TTL 字段值是 128,这往往意味着如果这个数据再经历 128 跳还没到达目的地就将被丢弃。当 IP 协议遇到一个 TTL 为 0 的数据报时,应当马上将其丢弃,并向数据报的源地址发送 TTL 超时的 ICMP 报文以通知发送者。

一个充分利用了 TTL 特性实现的网络工具是 traceroute。traceroute 程序利用逐次构造并发送 TTL 从 1 开始依次递增的 IP 数据报,并接收中途路由器返回的 ICMP TTL Timeout 报文来探测从当前主机到任一目标 IP 地址所经历的所有路由器的地址。

Protocol

Protocol 是一个 8 bits 的字段,它用于标识 IP 数据报所运送的载荷属于何种上层协议,最常见的 Protocol 字段值有 1 – ICMP、6 – TCP、17 – UDP 等。这个列表中列出了所有 Protocol 字段取值对应的上层协议及它们的详细信息。

Header Checksum

Header Checksum 字段长 16 bits,是 IP 头部的校验和字段。该用于对 IP 头部进行校验,以帮助 IP 协议检查出 IP 数据报头部在链路层转发过程中可能出现的误码情况。校验和是一种简单的差错检测方法,校验和值是一个无符号整数。以要求的校验和的字长为单位对原始数据分组,然后分别将它们相加,忽略掉在求和中溢出的部分,将得到的结果按位取反即为这段数据的校验和。如果原始数据的长度不是校验和字长的整数倍,那么对原始数据的末尾进行补 0 处理,直到其长度等于校验和字长的整数倍。下面是一个用 C 语言实现 16 位校验和计算的例子:

IP 头部 Checksum 字段的计算方法是,先将 IP 头部其他字段填充好,再将 Checksum 字段置为 0,对整个头部执行一次校验和计算,最后将计算结果填充到 Checksum 字段中。考察校验和的计算方法后不难发现,如果此时再对整个 IP 头部执行一次校验和计算,计算结果必为 0。当 IP 网络中一个设备收到 IP 数据报时,它首先会检验数据报头部是否在传输过程中发生了差错;检测方法就是利用了上述校验和的性质,只需对 IP 数据报头部部分求一次检验和,判断计算结果是否为 0,如果不为 0,则说明头部中出现了差错,必须丢弃这个数据报。

需要注意的是,IP 只对它的头部进行校验,计算校验和并不包括 IP 携带的载荷数据部分,IP 不保证它携带的载荷在传输过程中不发生差错。也就是说,如果一个 IP 数据报在传输过程中发生了误码,但误码只发生在载荷部分,IP 并不能检测这个差错,这个包含差错的数据报同样将被送到目的主机。对数据载荷的差错检验应该由上层协议来完成。

Source Address

32 bits 长,数据报发送者的 IP 地址。

Destination Address

32 bits 长,数据报目的主机的 IP 地址。

Options

Options 是 IP 头部中最后一个字段,它是不定长字段,也是一个可选的选项,一个 IP 头部中可以包含零个或多个 Options,用于在 IP 头部中添加附加的选项信息。IP 头部中的选项一共有如下两种情形:

  • 仅由一字节的选项类型(option-type)组成,没有附加数据;
  • 由一字节选项类型、一字节选项数据长度和不定长的选项数据组成。

其中选项类型依次由以下三部分构成:

  • 1 bit 拷贝标志(copied flag),这个标志位决定 IP 数据报发生分片时是否在分片的数据报中拷贝本选项,取值 0 表示不拷贝,取值 1 表示拷贝。
  • 2 bits 选项类别(option class)
  • 5 bits 选项号(option number)

RFC 791 中定义了如下几种选项:

类别 选项号 数据长度 描述
0 0 标志选项字段的结束,只占一个字节
0 1 没有选项,在选项与选项之间起填充作用,用于对齐各个选项的起始位置,占一个字节
0 2 11 安全选项。
0 3 变长 松散源路由选项。
0 9 变长 严格源路由选项。
0 7 变长 路由追踪。用于追踪数据报在网络中经历的路由。
0 8 4 Stream ID。用于运载卫星网络(SATNET)数据流的 id。
2 4 变长 Internet 时间戳。

有关 options 字段更详细的信息,请参阅 RFC 791 文档。

IP 数据报分片与重组

上文中提到,理论上最大的 IP 数据报可以长达 65,535 字节。IP 是建立在数据链路层之上的网络层协议,一个 IP 数据报从源主机出发到达目的主机的过程中,往往会经历多个不同物理网络,其链路层实现可能各不相同。在分组交换网链路层中,IP 数据报与链路层的帧往往是一一对应的,一个链路层帧携带一个 IP 数据报。而链路层对一帧的最大长度是有限制的,这个最大长度通常远小于 65,535 字节,例如 IEEE802.3 以太网的最大帧长是 1500 字节。在软件中,会根据链路层最大帧长的实际情况为链路层接口配置一个 MTU(最大传输单元) 值,表示这个接口一次最大能传输的字节数。

不同链路层的最大帧长度可能不尽相同,因此在互联网中很可能会出现下面的情形:某主机从 A 接口收到一个数据报,在查路由表之后决定将其从 B 接口转发给下一站,而 B 接口所在的链路层的 MTU 小于数据报的长度,不足以直接运载这个数据报。当这种情形发生时,IP 将根据该数据报头部中 flag 字段的情况作如下两种处理:

  1. 如果 DF 位是 1,说明该数据报不允许分片,丢弃这个数据报并向它的源地址发送“目标不可达:要求分片”的 ICMP 报文。
  2. 如果 DF 位是 0,则根据具体情况将数据报拆分成两片或多片,依次发往下一站。

当一个数据报需要分片时,首先根据具体的 MTU 值将原始数据报的载荷数据拆分成两份或多份,除最后一份之外,每一份的长度应该是 8 字节的整数倍以保证对齐。然后创建相同数量的新 IP 数据报,将原始数据报的头部复制到这些新数据报的头部中,将拆分后的数据依次填入到新的数据报的载荷中。再依次修改新数据报头部中的 flag、total length、fragment offset 等字段,除最后一个数据报外的所有数据报 flag 字段的 MF 标志都修改为 1,所有数据报的 total length 字段都修改为数据报实际的总长度,所有数据报的 fragment offset 字段修改为分片载荷在原数据报载荷中的偏移。最后一个数据报做必要的补 0 对齐处理。

将分片后的数据报依次发送给下一站。

当 IP 收到分片的 IP 数据报时,在必要时(例如分片已到达目的主机)将它们收集起来并把各自的载荷连接为整体。IP 把头部中 identification、source address、destination address 和 protocol 相同的 IP 数据报归为一组,并根据 fragment offset 字段的值决定各个分片的先后顺序,在所有分片都到达时,原始数据报的载荷就拼装好了。

后续博文还将继续讨论与 IP 路由相关的话题。

(允许转载本文,转载请注明出处:http://luodichen.com/blog/?p=476 )

参考文献
[1] Information Sciences Institute of USC, INTERNET PROTOCOL DARPA INTERNET PROGRAM PROTOCOL SPECIFICATION, RFC 791, Sep 1981; tools.ietf.org/html/rfc791
[2] Wikipedia. Differentiated services[EB/OL]. https://en.wikipedia.org/wiki/Differentiated_services
[3] Wikipedia. IPv4[EB/OL]. https://en.wikipedia.org/wiki/IPv4
[4] W. Richard Stevens, TCP/IP 详解 卷1:协议[M]. 机械工业出版社, 2000.

IP 与路由(一)

IP(Internet Protocol网际协议) 是 TCP/IP 协议族中最核心的部分。IP 是一个网络层协议,为处于不同网络中的主机提供端到端通信的服务。IP 协议采用分组发送的方式工作,只需要下层协议提供分组交换服务,不需要在通信前建立专用的连接。IP 协议只提供“尽力而为”的分组传送服务,不保证传送的分组不丢失、不重复、不出差错,也不保证分组能按顺序到达。因此,IP 的上层协议还应当视情况实现差错控制、重传等功能。

目前 IP 有两个在互联网中应用的版本,分别是 Internet Protocol version 4(IPv4)Internet Protocol version 6(IPv6),本文主要讨论的是 IPv4,如无特殊说明,下文中的“IP”均指 IPv4。

IP 地址

所有使用 IP 协议互联的主机都配置有 IP 地址,IP 地址是 TCP/IP 网中主机的标识,IP 路由的实现依赖于 IP 地址。IP 地址是一个非常重要的概念,也是 TCP/IP 在日常交流中被提及最频繁的概念,以至于在日常语境中“IP”一词往往特指“IP 地址”。

IP 地址是一个 32 位无符号整数,由 4 个字节组成,因此理论上最多可以有 232 约 42.9 亿个 IP 地址。为了便于表达和记忆,IP 地址通常不直接用整数表示,而用点分十进制的形式表示——从高位到低位依次用 4 个范围为 0~255 的十进制数表示 IP 地址的 4 个字节,中间用点号分隔。例如,本站目前所在服务器的 IP 地址是 107.182.176.178,用十进制数表示这个 IP 地址是 1807134898,用十六进制数表示是 0x6bb6b0b2。

IP 地址是 Internet 上的公共资源,目前由互联网名称与数字地址分配机构(Internet Corporation for Assigned Names and Numbers, ICANN)负责管理和分配。IP 地址的分配是根据地理区域分层次进行的,全球共有如下五个分布在不同地区的区域互联网注册管理机构(Regional Internet Registries, RIRs):

AfriNIC 非洲互联网络信息中心
APNIC 亚太互联网络信息中心
ARIN 美国互联网数字地址注册局
LACNIC 拉丁美洲和加勒比地区互联网络信息中心
RIPE NCC 欧洲互联网络协调中心

下面的地图展示了上述几个区域互联网注册管理机构管辖的范围,图片来源于维基百科 Regional Internet registry 词条。

Regional_Internet_Registries_world_map图 1 全球五个区域互联网注册管理机构管辖的范围

ICANN 将整个 IP 地址空间划分为若干块分配给上述几个区域互联网注册管理机构,区域互联网注册管理机构再将他们所有的 IP 块分成更小的块,分配给所管辖的互联网服务提供商或其他网络机构;互联网服务提供商最终将 IP 地址分配给每一台接入互联网的设备[1]

并不是所有的 IP 地址都应用在 Internet 中,IP 地址空间中还有相当可观数量的 IP 地址被保留用于组建私网、广播、多播及其他用途,以这些地址为目的地址的 IP 报文不会被 Internet 中的路由器转发。下面是这些 IP 地址的列表:

起始地址 终止地址 数目 用途
0.0.0.0 0.255.255.255 16,777,216 当前网络
10.0.0.0 10.255.255.255 16,777,216 私有地址
100.64.0.0 100.127.255.255 4,194,304 共享地址空间
127.0.0.0 127.255.255.255 16,777,216 环回
169.254.0.0 169.254.255.255 65,536 本地链路
172.16.0.0 172.31.255.255 1,048,576 私有地址
192.0.0.0 192.0.0.255 256 IETF 协议分配
192.0.2.0 192.0.2.255 256 文档与示例用
192.88.99.0 192.88.99.255 256 IPv6-IPv4 中继
192.168.0.0 192.168.255.255 65,536 私有地址
198.18.0.0 198.19.255.255 131,072 网络基准测试用
198.51.100.0 198.51.100.255 256 文档与示例用
203.0.113.0 203.0.113.255 256 文档与示例用
224.0.0.0 239.255.255.255 268,435,456 IP 多播
240.0.0.0 255.255.255.254 268,435,455 保留地址
255.255.255.255 1 广播地址

除去上述保留的地址之后,真正用于 Internet 的 IP 地址约有 37.0 亿个。Internet 已经以难以置信的高速度发展了二十多年,过去的十年中,互联网用户数每年都有数以亿计的增长,接入 Internet 的设备越来越多,IP 地址资源变得越来越稀缺,Internet 必须面对 IP 地址即将用尽的现实。相比于 IPv4,IPv6 拥有多得多的地址数,可以解决地址不够用的问题,目前 Internet 已经开始向 IPv6 过渡了。此外,NAT(Network address translation) 技术的广泛运用也一定程度上缓解了 IP 地址数紧张的问题,关于 NAT 的话题将在后续博文中详细讨论。

IP 子网

IP 的设计目标是连接多个本地网络,在多个网络之间建立一个互联系统。网络中的每一台主机都至少拥有一个唯一的 IP 地址,一个 IP 地址由网络号和主机号两部分组成。网络号用于区分整个网络中不同的子网,主机号用于区分同一子网下具体的主机。

将一个 IP 地址截成两段,较高位的一段是网络号,较低位的一段是主机号。划分子网时可以根据具体的情况在已分配的所有 IP 地址范围内任意选取网络号和主机号的长度。值得注意的是,IP 网络是具有层次结构的,一台子网内主机所在的整个网络可能只是另一个更大的网络中子网的一部分。网络的层次结构也表现在 IP 地址上,IP 地址中的主机号可以再次划分为一个子网号和一个子网内的主机号。下图是一个例子。

ip-subnet图 2 IP 地址 125.221.228.23 所对应网络号、子网号和主机号的情况

网络中所有的主机都配置有 IP 地址,但因为 IP 地址是由网络号与主机号两个部分组成的,还需要配置子网掩码使程序能区分 IP 地址中的网络号和主机号。子网掩码的形式与 IP 地址一样也是一个 32 位整数,用点分十进制表示;在一个子网掩码中,网络号部分所在的位全为 1,主机号部分所在的位全为 0。例如,上图中的 IP 地址所在子网的子网俺码是 255.255.255.0。IP 地址和它所对应的子网掩码求按位与运算后得到的结果正好是该地址的网络号;IP 地址和它所对应的子网掩码的反码求按位与运算后得到的结果正好是该地址的主机号。

在需要同时表示 IP 地址和它的子网划分时,还有一种更简便的形式,表示方法是在一个 IP 地址之后加上一个斜杠(/)再写上子网掩码中“1”的个数。如上图中的 IP 地址与子网划分可以这样表示:125.221.228.23/24。

子网号为全 0 的 IP 地址被保留用于表示网络号,不能配置给网络中的主机;另外,子网号为全 1 的 IP 地址也是保留的,它用于表示子网的广播地址。例如上图中的 IP 地址所在的网络号是 125.221.228.0,广播地址是 125.221.228.255。

后续博文将继续讨论 IP 报文的细节及 IP 路由的工作方式。

(允许转载本文,转载请注明出处:http://luodichen.com/blog/?p=402 )

参考文献
[1] ICANN. Beginner’s Guide to INTERNET PROTOCOL (IP) ADDRESSES, 2011.
[2] Wikipedia. IPv4[EB/OL]. https://en.wikipedia.org/wiki/IPv4

动态规划与编辑距离问题

动态规划Dynamic Programming)是一种精妙的算法设计技巧,在多种成熟的算法模型中都有动态规划思想的运用。

首先考虑一个简单的爬楼梯问题:一段楼梯共有 n 级阶梯,每次可以向上爬 1 级或 2 级,问一共有多少种上楼梯的方法。

假设在一段楼梯中,爬上第 i 级阶梯一共有 Si 种方法,容易观察到存在 Si = Si-2 + Si-1 (i = 3, 4, 5, …, n)的递推关系,同时显而易见地,有 S1 = 1, S2 = 2 的初始条件。因此,要求 Sn 的值,只需要通过递推关系先后求出 S3, S4, S5, … Sn 的值即可。

存在递推关系是一个问题可以用动态规划思想求解的必要条件。像上述求解爬楼梯问题一样,用动态规划求解一个规模为 n 的问题时,先考虑规模为 1, 2, 3… 等子问题是否有显而易见的解,再找出递推关系,利用递推关系逐步求解更大规模子问题的解,直到最终解出规模为 n 的问题。

动态规划思想经常用于解决最大、最小、最短、最优的路径等问题,在解决这类问题时,要确保找到的递推关系在每一步的计算结果都是符合问题中最大、最小、最短或最优要求的。另外,这类问题经常在每一步都有多个候选的解,需要用数组将这些候选解全部暂时存储起来。下面是一个经典的用动态规划求解的问题:一些数排列成一个三角形,从三解形的顶部出发,每次可以向左下或右下走一步,求走到最底部时经历的所有数之和最小的路径。

   2
  3 4
 6 5 7
4 1 8 3

首先,很显然的是,当这个问题的规模为 1(即只有一行)时,问题的解就是 2。设 Nij 表示这个三角形的第 i 行的第 j 个数(i、j 均从 0 开始计),Sij 表示从根出发到 Nij 可能的所有路径中经历所有的数(包括 Nij)的最小的和,可以得到如下的递推关系:Sij = min(Si-1 j, Si-1 j-1) + Nij。min(x, y) 表示 x, y 中较小的那个数。

然后逐步增加问题的规模,用递推关系解出每一步的结果:当子问题规模为 2、3、4(即 2 行、3 行、4 行)时,(Sn0, Sn1, …, Snn) 分别是 (5, 6)、(11, 10, 13)、(15, 11, 18, 16)。在最终的结果中选出最小的数 11 即为本问题的解。

下面的代码是上述算法的 Python 实现。

不同的问题递推关系中需要的已知条件可能各不相同,有的只需要前一步的结果有的需要前更多步甚至之前所有的结果;如上面的问题只需要前一步的结果,而爬楼梯问题则需要前一步和前两步的结果等。在编写程序时应当根据递推关系的特点暂存前一步或更多步的计算结果。

动态规划一个实用的应用是求编辑距离Edit Distance)。一个字符串可以经历有限次变换步骤转变成另一个字符串,假设每个步骤只允许在字符串的任意位置增加、删除或修改一个字符,由字符串甲转换到字符串乙可行的最少步骤数即是这两个字符串之间的编辑距离。编辑距离在 DNA 分析、拼写检查、语音识别、抄袭检测等多个领域都有应用。

例如,可以通过如下的三个步骤将单词“kitten”转变为“sitting”:

  1. kitten → sitten(k → s)
  2. sitten → sittin (e → i)
  3. sittin → sitting (→ g)

从源字符串经过一系列编辑动作转换为目标字符串的可行路径很多,求解编辑距离实质上就是寻找一条这样的最短路径,并得到它的长度。为了找到最短的编辑路径,可以运用上述的动态规划的思想。

前文中讲到,用动态规划求解问题,首先考虑一个较小规模的子问题是否有显而易见的解。对于编辑距离问题来说,“规模”存在于源字符串和目标字符串的长度两个维度,例如“将字符串 k 转变为字符串 s”是最小规模的一个子问题;“将字符串 ki 转变为字符串 s”与“将字符串 k 转变为字符串 si”为两个维度上不同的两个次小规模的子问题。显然,它们都有显而易见的解。

用下图的一个二维表格来表示上述编辑距离问题中每一个子问题的解的情况。

图 1 用二维表格表示一个编辑距离问题解的情况

在上述表格中,设 Cij 为第 j 行第 i 列的单元格,单元格 Cij 中将填入的数字表示源字符串的长度为 i 的子字符串转换为目标字符串长度为 j 的子字符串的编辑距离。例如,C45 表示字符串 kitt 转换为字符串 sitti 的编辑距离。特别地,当 i 或 j 为 0 时的单元格表示的是空源字符串或空目标字符串。

上述的表格第 0 行表示一个字符串转换为空字符串的编辑距离,显而易见地,这一行中所有单元格的数值是所对应的源字符串的长度;同理,上述表示中第 0 列表示一个空字符串转换为目标字符串的编辑距离,这一列中所有单元格的数值是所对应的目标字符串的长度。所以有 C0p = p, Cq0 = q,可以简单地填满第 0 行和第 0 列的所有单元格如下:

图 2 填写表格的第 0 行和第 0 列

接下来,考虑这个问题的递推关系。先假设 Si 表示源字符串长度为 i 的子字符串,Dj 表示目标字符串长度为 j 的子字符串,所以单元格 Cij 表示的是字符串 Si 转换为字符串 Dj 的编辑距离。由于编辑距离的定义中允许每步插入、删除或修改一个字符,因此由字符串 Sm 转换为字符串 Dn 有如下三种可行的方案:

  • 在由 Sm 转换的字符串 Dn-1 的末尾增加一个字符,编辑长度计 1,即 C’mn = Cm n-1 + 1;
  • 在由 Sm-1 转换的字符串 Dn 的末尾删去一个字符,编辑长度计 1,即 C”mn = Cm-1 n + 1;
  • 在由 Sm-1 转换的字符串 Dn-1 的末尾修改一个字符,编辑长度计 1,即 C”’mn = Cm-1 n-1 + 1;特别地,如果源字符串的第 m 个字符正好与目标字符串的第 n 个字符相同,则此次不必修改字符,即 C”’mn = Cm-1 n-1

由于编辑距离有路径最短的要求,必须在每一步转换中选择编辑长度最短的方案,以达到局部最优解。因此,Cmn 最终的结果可表示为 Cmn = min(C’mn, C”mn, C”’mn),min(a, b, c) 表示取 a, b, c 中最小的数。因为 Cmn 的结果只与 Cm-1 n、Cm n-1 和 Cm-1 n-1 三个数有关,所以上述式子构成解决编辑距离问题的递推关系。

有了递推关系,就可以从初始条件出发,逐步推算出每一个阶段的编辑路径了。在上文的例子中,从上向下、从左向右逐步填写二维表格最终如下:

图 3 通过递推关系逐步推算出所有单元格中的值

取表格中右下角单元格中的值,即是最终要求的编辑距离。如以上的例子中,字符串 kitten 到字符串 sitting 的编辑距离是 3。

下面是用 Python 语言实现的求解两个字符串编辑距离的程序代码。

(允许转载本文,转载请注明出处:http://luodichen.com/blog/?p=410 )

参考文献
[1] Wikipedia. 编辑距离[EB/OL]. https://zh.wikipedia.org/wiki/%E7%B7%A8%E8%BC%AF%E8%B7%9D%E9%9B%A2
[2] Wikipedia. Edit Distance[EB/OL]. https://en.wikipedia.org/wiki/Edit_distance

Brainfuck 语言与图灵机

Brainfuck 语言是在 1992 年由瑞士一名学生 Urban Müller 设计的[1]。Brainfuck 是一种语言要素极精简的计算机语言,它没有一般高级语言拥有的关键字、运算符、标识符、语句等概念,甚至连汇编语言的操作数概念都没有。因此,Brainfuck 语言的编译器和解释器都十分容易实现,并且它们的代码可以非常短小,已经有人实现了可执行文件只有 100 字节的 Brainfuck 编译器。

Brainfuck 语言一共只有 8 个指令,颇有些简陋的语言设计使其代码其实很难编写,写成的代码看上去也是一片混乱,可读性很差。正如它名字所说的,这不是一门实用的程序设计语言,仅是一种程序员自娱自乐的工具。尽管如此,它仍然是一门图灵完备的语言,理论上可以用它实现任何其他计算机程序设计语言能实现的程序。另外,学习 Brainfuck 语言也对理解计算机组成原理和计算机程序原理有一些帮助。

Brainfuck 的全部 8 个指令都由一个单字符表示,分别是 +、-、<、>、.、,、[ 和 ]。Brainfuck 定义了一块内存空间和一个指针,指针指向内存空间的某个地址,指令可以移动指针和操作指针指向的内存单元。Brainfuck 每个指令的作用如下所述。

  • + 指针指向内存单元的值加 1;
  • – 指针指向内存单元的值减 1;
  • < 指针向左移动 1 个单元;
  • > 指针向右移动 1 个单元;
  • . 以字符形式输出指针指向的内存单元的值;
  • , 以字符形式输入到指针指向的内存单元;
  • [ 测试指针指向的内存单元值是否为 0,如果是,跳到对应的 ] 指令的下一个指令处继续执行;
  • ] 测试指针指向的内存单元值是否非 0,如果是,跳到对应的 [ 指令的下一个指令处继续执行。

相比于一门编程语言,Brainfuck 更像是一个简易计算机系统的指令集。语言本身定义了一种包含运算器、内存、寄存器和输入输出设备的计算机,而编程实现 Brainfuck 解释器实质上就是实现了这样一个虚拟机的实例。前面讲到,Brainfuck 是一种很容易实现解释器和编译器的语言,下面是我用 Python 实现的一个 Brainfuck 解释器

Brainfuck 语言缺少基本运算指令,甚至缺少数据传送指令,名副其实,用 Brainfuck 编写程序是一件并不那么愉快的事情。下面是一段用 Brainfuck 编写的可以输出一个指定字符串的 Brainfuck 代码的程序,实际上只是按每个字符的 ASCII 码数值输出了相应数目的自加指令,得到的输出会非常长。为了使输出的代码变得短一些,还有很多发挥技巧的空间,但我不太想这样做了。

>>>>+++++[>+++[>+++[<<<+>>>-]<-]<-]<
[<+<+<+>>>-]<<.>+.>
+[>,[<<<>>>-]<]

尽管 Brainfuck 不适合用于编写实用的计算机程序,但它存在的另外一个意义是很直观地描述了一个图灵机的原型。图灵机并不是一台具体的计算机,而是英国数学家阿兰·图灵于 1936 年提出的一种抽象计算模型[2]。图灵机是现代电子计算机的理论基础。

通俗描述的图灵机包含以下四个部分:

  • 一条(无限长)的纸带,纸带分成无穷多个格子,每个格子中可以记录一个数字或符号;
  • 一个读写头,可以在纸带上左右移动,可以读取或修改当前所在格子中的符号;
  • 一个状态寄存器,可以保存机器当前的全部状态;
  • 一套规则表,可以根据当前的状态以及当前读写头指向的纸带中的字符查表决定下一步应该做什么操作。

图灵机有一个特殊的状态,称作停机状态。图灵机必须在有限次的执行步骤后进入停机状态,此时计算完成。图灵认为,图灵机模拟了人类解决数学问题的过程,理论上可以解决任何人类需要手工完成的数学计算。

Brainfuck 语言的描述与图灵机高度契合。在 Brainfuck 解释器中,Brainfuck 的内存数组是图灵机中的那条纸带,指针是图灵机的读写头,额外的几个变量是图灵机的状态寄存器,而 Brainfuck 程序源代码则是图灵机的规则表。Brainfuck 语言解释器实际上成了一个运行在计算机上的虚拟图灵机原型。

图灵机与现代计算机关系密切,是现代电子计算机的理论基础;但如上所述,图灵机并没有描述计算机在硬件上具体如何实现。真正设计了现代电子计算机体系结构的是被称为电子计算机之父的美国科学家约翰·冯·诺伊曼。冯·诺伊曼指出了一个实际可行的电子图灵机的结构:一部由运算器、控制器、存储器和输入输出设备组成的,由程序控制运行的机器,被称为冯·诺伊曼系统结构。

冯·诺伊曼提出的电子计算机系统结构一直被沿用至今,今天我们使用的所有计算机均是建立在这个体系结构之上的。

向图灵、冯·诺伊曼及其他所有参与设计建造电子计算机的先驱们致敬。

(允许转载本文,转载请注明出处:http://luodichen.com/blog/?p=391 )

参考文献
[1] Wikipedia. Brainfuck[EB/OL]. https://en.wikipedia.org/wiki/Brainfuck
[2] Wikipedia. 图灵机[EB/OL].https://zh.wikipedia.org/wiki/%E5%9B%BE%E7%81%B5%E6%9C%BA
[3] 吴军. 文明之光(第三册)[M]. 人民邮电出版社, 2015.

DNS:域名系统(二)

文章《DNS:域名系统(一)》从 DNS 系统的结构和工作原理的角度描绘了 DNS 系统的基本概貌,本文将继续深入探讨 DNS 的话题,以 DNS 客户端的视角窥探 DNS 协议的细节。

在 Internet 中,DNS 客户端与服务器之间使用 TCP 或 UDP 协议传送 DNS 消息,服务器端开放的端口号均为 53。在大多数情况下,客户端通过 UDP 协议向服务端发送 DNS 查询请求,服务端也通过 UDP 协议向客户端发送响应。在客户端或服务端认为一次查询或响应需要运载的数据量超过 512 字节时,需要改用 TCP 协议来传送请求或响应,后文将对这种情形有所解释。

DNS 请求与响应的消息均由消息头部与消息实体两部分组成,请求与响应的消息头部的格式是一致的,下面是 DNS 消息头部结构的图示[1]

                                    1  1  1  1  1  1
      0  1  2  3  4  5  6  7  8  9  0  1  2  3  4  5
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                      ID                       |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |QR|   Opcode  |AA|TC|RD|RA|   Z    |   RCODE   |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                    QDCOUNT                    |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                    ANCOUNT                    |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                    NSCOUNT                    |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                    ARCOUNT                    |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
  • ID 是一个 16 位的标识符,由客户端根据具体情况设置,当服务端回应这个请求时,会将同样的 ID 值填写在响应消息头部的 ID 字段中。
  • QR 是一个占 1 位的字段用于标记这个 DNS 消息是请求(Query)还是响应 (Response)。当 DNS 消息是一个请求消息时,这个字段被设置为 0,反之当 DNS 消息是一个响应消息时,这个字段被设置为 1。
  • Opcode 是一个 4 位的操作代码,它由客户端设置,服务器在响应中会填入与对应请求相同的 Opcode。目前,Opcode 有三种有效的取值,它们的值与含义如下:
    • 0 – 标准请求。
    • 1 – 反向解析请求,用于查询 PTR 记录。
    • 2 – 服务器状态查询。
  • 接下来是一个包含 4 位的 flag,从低到高依次是 AA、TC、RD 和 RA,每个 flag 的含义分别如下:
    • AA(Authoritative Answer)标记只在响应消息中有效,置位表示该响应来自请求域名对应的域中的授权服务器。
    • TC(Truncation)标记表示该消息因传输长度的限制而被截断。通常发生在客户端以 UDP 协议发起解析请求,而服务端的全部响应超过 512 字节时,服务端将响应在 512 字节处截断,并置位 TC,提示客户端收到的响应可能是不完整的。
    • RD(Recursion Desired)递归解析请求,要求 DNS 服务端以递归解析的方式处理请求。由客户端在请求中设置,服务端在响应中置位与对应的请求一致。值得注意的是,DNS 协议不强制要求所有 DNS 服务器提供递归解析的功能,因此即使客户端在请求中置位 RD,也有可能不会得到期望的响应,可以用下面提到的 RA 标记判断服务器是否支持递归解析。
    • RA(Recursion Available)递归可用。这个标记由服务端设置,在响应中有效。当 RA 置位时,表示该服务器支持递归解析,向它发起的递归解析请求都能得到期望的结果。
  • Z 所在的位置是一段 4 位的保留区域,必须填为 0。
  • RCODE(Response code)是由服务端在响应中设置的 4 位响应代码,不同的值含义分别如下:
    • 0 – 没有错误。
    • 1 – 格式错误。服务器无法解释请求。
    • 2 – 服务器失败。因为服务器的某些故障而不能完成解析请求。
    • 3 – 名字错误。这个错误代码只会出现在授权的域名服务器的响应中,含义为请求查询的域名不存在。
    • 4 – 未实现。当前服务器不支持这种查询。
    • 5 – 拒绝。服务器主动拒绝当前的查询请求。
    • 6 ~ 15 – 为其他失败保留的代码。
  • QDCOUNT 是一个 16 位的整数,表示消息实体中问题的数量。
  • ANCOUNT 是一个 16 位的整数,表示消息实体中答案的数量。
  • NSCOUNT 是一个 16 位的整数,表示消息实体中 NameServer 记录的数量。
  • ARCOUNT 是一个 16 位的整数,表示消息实体中授权记录的数量。

值得注意的一点是,当客户端程序通过 UDP 协议发起一次 DNS 解析请求,后又收到一个 TC 置位的服务器响应时,客户端程序一般要用 TCP 协议与服务器建立连接,重新发起一次解析请求以获得完整的解析结果。

消息实体紧随消息头部,消息实体由问题部分和资源记录部分组成,DNS 请求的消息实体只包含问题部分,DNS 响应的消息实体既有问题部分又有资源记录部分。其中资源记录又分三大块:DNS 回答资源记录、授权服务器资源记录和附加的资源记录。一个包含消息头部和完整消息实体的 DNS 消息如下所示。

    +---------------------+
    |        Header       |
    +---------------------+
    |       Question      | the question for the name server
    +---------------------+
    |        Answer       | RRs answering the question
    +---------------------+
    |      Authority      | RRs pointing toward an authority
    +---------------------+
    |      Additional     | RRs holding additional information
    +---------------------+

Question 是 DNS 解析请求的问题部分,在 DNS 响应消息中也包含这个部分,内容与对应的请求消息中的 Question 一致。Question 中有请求解析的域名、请求的资源类型和网络类型。Question 的结构如下所示。

                                    1  1  1  1  1  1
      0  1  2  3  4  5  6  7  8  9  0  1  2  3  4  5
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                                               |
    /                     QNAME                     /
    /                                               /
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                     QTYPE                     |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                     QCLASS                    |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

QNAME 是被查询的域的域名,它的长度是不定长的。在《DNS:域名系统(一)》中提到,域名系统树中任意一个结点域名是由该结点到根结点的路径上经过的所有结点的标签一起组成的,书写上用圆点分隔这些标签(label),如 work.luodichen.com 等。域名在 QNAME 中的格式与书写格式稍有不同,同样是从枝叶到树根的标签依次排列,但每个标签之前还有一个字节表示该标签的长度。注意,树根的 NULL 结点也要包含在其中,树根总是以一个值为 0 的字节表示,同时也是 QNAME 字段结束的标识。例如域名 work.luodichen.com 在 QNAME 中存储形式的 C 语言表示如下:

特别地,当解析的目标域名是根域名时,QNAME 的格式同样遵循上面所说的规则,向 QNAME 中填入根域名的长度 0,其后不再有任何字符。

QTYPE 是一个 2 字节的查询类型字段,表示希望解析域名的资源记录的类型,DNS 协议规定的资源记录类型较多,有些是已经废弃不用的,有些是为了适应互联网的发展新加的。下面的代码列出了几种常见的资源记录类型的缩写、数值和说明。

QCLASS 字段表示网络类型,一般设置为 1(Internet)。

DNS 响应消息中包含 Answer、Authority 和 Additional 等三组资源记录,每一组资源记录都有 0 个或多个资源记录,上文已经提到,每组资源记录的数目在协议头部对应的字段中。每个资源记录的格式都是一致的,它们的结构如下所示:

                                    1  1  1  1  1  1
      0  1  2  3  4  5  6  7  8  9  0  1  2  3  4  5
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                                               |
    /                                               /
    /                      NAME                     /
    |                                               |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                      TYPE                     |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                     CLASS                     |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                      TTL                      |
    |                                               |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                   RDLENGTH                    |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--|
    /                     RDATA                     /
    /                                               /
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

NAME 是变长字段,表示该资源记录对应的域名,它的格式可能是压缩形式的,后文中将讨论 DNS 消息中压缩名字的格式。

TYPE 与 CLASS 与上文所说的 QTYPE 和 QCLASS 类似,表示这个资源记录的类型与网络类型。

TTL 是一个 32 位的整数,表示这个资源记录的生存时间(秒),TTL 是一个资源记录能在 DNS 缓存中生存的最长时间。

RDLENGTH 是一个 16 位的整数,它表示 RDATA 字段的长度(字节)。

RDATA 是一个变长的字段,根据资源记录类型(TYPE)的不同而有不同的格式,例如在 A(IP 地址)记录中,RDATA 是一个 32 位的 IP 地址。更多资源记录类型对应的 RDATA 格式请参考文本参考文献中提到的 RFC 1035 文档和其他相关的 RFC 文档。

为了节省 DNS 查询和响应的网络流量,DNS 协议使用一种压缩的策略来消除 DNS 消息中域名相关字段可能产生的重复内容,从而减小 DNS 消息的长度,这对于一种主要使用 UDP 来传送消息的协议来说是很重要的。前文中提到,一个域名可以表示为多个标签连续排列,并在每个标签前用一个字节表示标签长度的方式来表示,为了下文描述方便,将这个字节称为该标签的“标签头”。此外,DNS 协议还允许使用一种指针的方式引用消息实体中当前标签所在的位置之前任意位置出现过的域名或域名的一部分。DNS 规定,当一个“标签头”的高 2 位都为 1 时,这个标签头余下的 6 位以及标签头后一个字节的 8 位共 14 位构成一个指针。指针的整数数值是一个偏移量,偏移的起始位置是消息实体的第一个字节,指针指向的是另一个标签头,因为指针的目标可能是一个普通的标签头也可能是另一个带指针的标签头,因此需要递归地处理新的标签头,直到遇到根结点标签。下面是一个在 Answer 资源记录中 NAME 字段以指针表示的实例,可以看到 Answer 资源记录的 Name 字段是 0xc00c,指针偏移值是 12,指向 Queries 中 Name 字段的一个域名 luodichen.com。

dns-compress图 1 解析域名 luodichen.com 的响应消息

在编写文本的同时,还用 C++ 开发了一个同时支持 Windows 和 Linux 平台的 DNS 客户端库,源码托管在 GitHub,查看

(允许转载本文,转载请注明出处 http://luodichen.com/blog/?p=367 )

参考文献
[1] P. Mockapetris, DOMAIN NAMES – IMPLEMENTATION AND SPECIFICATION, RFC 1035, November 1987; www.ietf.org/rfc/rfc1035.txt

HTTP 协议概貌

HTTP 协议诞生于 1990 年,最初被设计用于传输 WWW 的超媒体数据。在二十多年的互联网发展过程中,web 应用始终都是互联网重要角色,HTTP 协议也得到了广泛的应用。HTTP 协议发展时间较长,在开发上基于 HTTP 的服务端与客户端组件非常丰富,用 HTTP 协议搭建不论是 B/S 模式的应用程序还是 C/S 模式的应用程序都十分简便。再加上它具有很好的灵活性,在互联网技术高度发达的今天,除了常规的 web 应用之外,HTTP 协议还广泛被运用于各种多媒体流服务、下载服务、桌面和移动客户端应用等。

HTTP 是一个基于请求/响应模型的协议,用户代理程序(user agent,对于 web 应用来说,是浏览器,以下简称“用户”)向原始服务器(origin server,以下简称“服务器”)发送 HTTP 请求(request);服务器收到请求后,解析请求并向用户发送相应的 HTTP 响应(response)*

HTTP 请求与响应消息格式都由以下几个部分按顺序组成:

  • 起始行;
  • 消息头部;
  • 标识头部结束的空行;
  • 可选的消息主体(message body)。

除了消息主体可能存在二进制格式的信息之外,HTTP 协议的其他部分都由 ASCII 字符流组成。消息各部分按“行”分割,每一行以 CRLF 结束。像上面提到的,HTTP 的请求和响应消息的第一行都称作起始行,起始行中包含请求资源的类型、资源位置、HTTP 版本号、响应的状态等信息,以下将具体讨论 HTTP 协议的起始行。

请求起始行

HTTP 请求的起始行由方式(method)、资源ID(URI)和协议版本号组成,三个部分以空格分隔。下面是一个 HTTP 请求行的示例:

GET http://luodichen.com/ HTTP/1.1

这个请求起始行的含义是以 GET 方式向服务端请求URI http://luodichen.com/ 的资源,HTTP 协议版本号为 1.1。

GET 是最常见的请求方式,表示希望服务端返回请求 URI 所在的资源数据。另外一个最常见的请求方式是 POST,POST 常用于像提交表单之类需要向服务端传送少量信息的场合,服务端收到 POST 请求之后,也可以视情况响应相应的消息。当发送一个 POST 请求时,需要将要传送的数据填写在消息主体中。除了 GET 和 POST 方式之外,HTTP 协议还定义了其他多种请求方式,要了解每种请求方式的详细情况请查阅参考文献中引用的 RFC 2616 文档。HTTP 1.1 协议中定义的所有请求方式如下:

OPTIONS
GET
HEAD
POST
PUT
DELETE
TRACE
CONNECT

请求 URI 可以是一个完整的 HTTP URL,如 http://luodichen.com/blog/,也可以是一个相对路径,如 /blog/。相对路径表示相对于服务器 HTTP 根目录的路径,当 URI 本身就是根目录时,应当将 URI 设置为 ‘/’。当 URI 是一个相对路径时,必须在请求的 HTTP 头部中包含 Host 字段,如 Host: luodichen.com。有关 HTTP 头部的详细情况将在下文中讨论。

URI 中还可以携带一些发送给服务端的参数,参数以符号 ‘?’ 开头,由 key=value 形式组成,每一组参数用符号 ‘&’ 分隔。当参数的 key 或 value 中含有一些特殊字符时,应当对它们进行 urlencode 编码。下面是一个典型的带有参数的 URI:

/login/?user=username&pass=pass%26%7bword%7d

响应起始行

响应的起始行在 RFC 中被称为状态行(status-line)。状态行依次由 HTTP 协议版本号、三位数数字状态码和原因语句组成,三者由空格分隔,中间无换行或回车符。

接收到请求之后,服务端根据具体情况会产生 5 类响应,这 5 类响应对应状态码的头一位数字 1-5。这些响应状态码的具体描述如下:

  • 1xx – 消息。请求已收到,将继续处理;
  • 2xx – 成功。请求已经成功收到,并且是合法的请求,且已经执行;
  • 3xx – 重定向。要求执行另一个动作;
  • 4xx – 客户端错误。请求包含错误的格式,或请求不能被通过;
  • 5xx – 服务端错误。请求格式应该是正确的,但服务端执行请求时发生了错误。

200 是最常见的响应代码,表示请求成功,请求所要求的信息已经包含在响应中。301 和 303 也是比较常见的响应代码,通常用于服务端要求跳转。其中 301 表示永久转移(Moved Permanently),303 表示临时跳转到另一个资源。404 是最常见的错误代码,它的含义是未找到(Not Found),当向服务端发送一个 GET 请求,而服务端没有找到请求 URI 指示的资源时,会响应 404 错误代码,提示用户端发送了不存在的 URI 请求。

除此之外还有很多 HTTP 状态码,下面是在 HTTP 1.1 中定义的所有状态码和他们对应的原因语句。

100 Continue
101 Switching Protocols

200 OK
201 Created
202 Accepted
203 Non-Authoritative Information
204 No Content
205 Reset Content
206 Partial Content

300 Multiple Choices
301 Moved Permanently
302 Found
303 See Other
304 Not Modified
305 Use Proxy
307 Temporary Redirect

400 Bad Request
401 Unauthorized
402 Payment Required
403 Forbidden
404 Not Found
405 Method Not Allowed
406 Not Acceptable
407 Proxy Authentication Required
408 Request Time-out
409 Conflict
410 Gone
411 Length Required
412 Precondition Failed
413 Request Entity Too Large
414 Request-URI Too Large
415 Unsupported Media Type
416 Requested range not satisfiable
417 Expectation Failed

500 Internal Server Error
501 Not Implemented
502 Bad Gateway
503 Service Unavailable
504 Gateway Time-out
505 HTTP Version not supported

关于这些状态更详细的说明,请参阅文末参考文献中引用的 RFC 2616 文档中的第 10 节。

HTTP 协议还允许服务端程序根据具体情况定义扩充的状态码,并且也有一些服务端程序这样做了。例如 nginx 定义了状态码 495、496、497、499 等[2]

头部字段

HTTP 的头部字段均为 key-value 形式,每个字段各占一行,行末由 CRLF 结束。其中有一些字段是请求或响应特有的字段,还有一些是既可能出现在请求中又可能出现在响应中的字段,称为通用字段。HTTP 1.1 协议定义全部通用头部字段列出如下:

Cache-Control
Connection
Date
Pragma
Trailer
Transfer-Encoding
Upgrade
Via
Warning

HTTP 请求特有的字段列出如下:

Accept
Accept-Charset
Accept-Encoding
Accept-Language
Authorization
Expect
From
Host
If-Match
If-Modified-Since
If-None-Match
If-Range
If-Unmodified-Since
Max-Forwards
Proxy-Authorization
Range
Referer
TE
User-Agent

HTTP 响应特有的字段列出如下:

Accept-Ranges
Age
ETag
Location
Proxy-Authenticate
Retry-After
Server
Vary
WWW-Authenticate

与数据实体有关的字段列出如下:

Allow
Content-Encoding
Content-Language
Content-Length
Content-Location
Content-MD5
Content-Range
Content-Type
Expires
Last-Modified

HTTP 协议同样允许用户端和服务端自行定义新的扩充字段。下文中会提及几个重要的头部字段的含义和协议细节,关于完整的 HTTP 协议头部字段的定义请参阅文末参考文献中引用的 RFC 2616 文档中的第 14 节。

定义用户端接受的内容格式

HTTP 协议用于传送多种格式的资源,用户端程序可能不能接受全部类型的格式,因此,在向服务端提交请求时,用户端程序可以在 HTTP 头部中设置 Accept 字段以告知服务端自己支持的资源格式。Accept 字段由一个或多个媒体范围组成,多个媒体范围之间用逗号分隔,媒体范围还可以接一个可选的 q 参数。下面是一个 Accept 字段的示例:

Accept: text/html,application/xhtml+xml,application/xml;q=0.9,image/webp,*/*;q=0.8

媒体范围的格式是 主类型/子类型,* 表示匹配所有的类型。q 参数是一个范围在 0-1 的浮点数,用于标识它所附加的媒体范围的优先级,当服务端同时支持 Accept 中列的多个媒体范围时,优先匹配 q  值较大的那个。当 q 值缺省时,它的默认值是 1。

q 参数在多个头部字段中都可能出现,含义均是在多个选项中选择时的优先级,关于这一点,下文不再赘述。

定义用户端接受的字符集

当 HTTP 用于传送文本内容时,由于不同的用户端程序可能接受不同的字符集,因此在向服务端提交请求时,用户端可以在 HTTP 头部设置 Accept-Charset 字段,以通知服务端自己支持的字符集。当支持多个字符集时,字符集之间用逗号分隔,并可以加上一个可选的 q 参数。下面是一个 Accept-Charset 字段的示例:

Accept-Charset: iso-8859-5, unicode-1-1;q=0.8

其他 Accept-XXX 字段

此外,还有用于压缩格式的 Accept-Encoding 字段、用于指示支持的语言的 Accept-Language 字段等。

消息内容的格式

当请求或响应中包含消息实体(内容)时,需要设置 Content-Type 指定消息的类型。这个字段是一个 MIME Type 值。下面是一个 Content-Type 的示例:

Content-Type: application/json

最初的 HTTP 协议在设计上并没有考虑处理状态和会话等问题,HTTP 是一个无状态的协议,直到 1994 年 Netscape 浏览器支持了一种叫 cookie 的技术。目前,cookie 技术在 web 应用中的地位已经十分重要,关于 HTTP cookie 的话题留到后续博文中讨论。


* 这里的 user agent / origin server 术语与 TCP/IP 中的 client / server 术语有微小的差别。术语 client / server 着重表示发起连接的程序(客户端)与接受连接的程序(服务端)之间具有一条可通信的链路,而 user agent / origin server 着重表示请求的发送者(user agent)与请求的接收和响应者(origin server)。事实上,在存在代理的情况下,user agent 与 origin server 之间不存在可以直接通信的链路,反之它们之间存在可直接通信的链路。

(允许转载文本,转载请注明出处:http://luodichen.com/blog/?p=344 )

参考文献
[1] R. Fielding, J. Gettys, J. Mogul, et al, Hypertext Transfer Protocol — HTTP/1.1, RFC 2616, June 1999; www.ietf.org/rfc/rfc2616.txt
[2] Wikipedia. List of HTTP status codes[EB/OL]. http://en.wikipedia.org/wiki/List_of_HTTP_status_codes

DNS:域名系统(一)

两年前写了《DNS协议及DNS客户端的实现》,最近一段时间计划重新写一个 DNS 客户端库,翻看当初写的文章,觉得太浅、太粗,甚至有错漏。于是决定在写 DNS 库的同时,写一篇博客,算是对以前文章的补充和修正。

将域名系统理解成一个“将 IP 地址和域名相互映射的分布式数据库”是片面的,域名系统面向的是域名和与域名相关联的资源,包括但不仅限于 IP 地址。域名系统的主要设计目标是(在网络中)实现一个统一的名字空间(name space)用于关联名字与其对应的资源(resources)。为了避免尤其是编码方式导致的一些问题,在域名中不应该包含网络 id、地址、路由或类似的其他信息[1]

DNS 是一个分布式的系统,由 Internet 上遍布世界各地的域名服务器组成;分布式域名系统的另一个含义是,在整个系统中,每一个节点的服务器都只存有部分域名的记录。当想要解析一个域名时,可能需要直接或间接地访问多个域名服务器才能得到结果。

DNS 的名字空间是一个树状结构,树中的每一个结点都拥有一个标签(label),规定标签的长度在 0-63 字符之间,其中 0 字符长的标签(NULL)由根结点保留。另外,兄弟结点之间不能有相同的标签,但非兄弟结点(即使是父子结点)之间可以拥有相同的标签。标签由英文字母(a-z, A-Z)、数字(0-9)和连字符(-)组成,不区分大小写,连字符不能连续出现,也不能出现在标签的第一个字符处。例如,label0、label-0 是合法的,而 -label、label–0 是非法的结点标签;label0 与 LABEL0 是等效的标签。每一个结点都对应一个域名,结点的域名由结点与根之间的路径上所有的结点(包括结点和根本身)的标签组成,这些标签从左到右依次排列,用点号(.)连接。下图展示了互联网中真实 DNS 名字空间的一部分,大部分结点还有其他子结点没有画出。

dns图1 互联网中 DNS 域名系统的一部分

根结点的直接子结点所在的域称为顶级域,对应的域名称为顶级域名,顶级域名目前由 ICANN(互联网名称与数字地址分配机构)负责分配和管理,关于域的分配和授权将在下文中讨论。从名称来看,顶级域可以分为以下几种:

  • 普通组织域名,通常为三个字符,是最常见的域名,如 com(商业机构)、net(网络服务)、org(非盈利性组织)等;
  • 国家域名,通常为两个字符,分配给世界各国使用,如 cn(中国)、tw(台湾)、us(美国)、jp(日本)等;
  • 用于地址到名字转换的特殊域 arpa。

最近 ICANN 还分配了一些由汉字组成的顶级域名,如“中国”等。

域名系统的正常运作离不开域名服务器(Server)和域名解析器(Resolver)。域名服务器中存储有它所管辖的域的域名和资源记录数据,并运行着一个域名服务程序,接受网络上的域名查询请求,并查询相应的记录,向查询者返回结果。域名解析器是一个客户端程序,它由应用程序调用,并通过网络接口访问一台或多台域名服务器,最终返回给调用者域名解析结果。

域名系统的中心是根结点,管理根结点所在域的服务器是根域名服务器,是最根本、最重要的域名服务器。全球共有 13 台根域名服务器,它们都有自己的域名,分别是 a.root-servers.net、b.root-servers.net,…,一直到 m.root-servers.net。这里的“一台根域名服务器”指的是逻辑上的数量,并不是指服务器的主机数量,事实上“一台”根域名服务器都由多台主机组成,它们共有同一个域名和 IP 地址。所有的根域名服务器都只存有全部顶级域名的记录,并只能提供对顶级域名的解析服务。

前面讲道,想要解析一个域名可能需要向多个域名服务器发起解析请求,这是由域名系统的层次结构以及授权机制决定的。ICANN 负责管理和分配全部顶级域名,并将顶级域名分别授权给所有这些域名的机构。例如,顶级域名 cn 由 ICANN 授权给 CNNIC(中国互联网络信息中心)管理。这些拥有顶级域名的二级域名机构可以布署域名服务器,并再授权给下一级的其他机构来管理他们的域名或子域名。这样,一个由根结点出发,逐级授权的域名系统就能建立起来了。

所有根域名服务器都是权威的(authoritative)域名服务器,权威域名服务器意味着它的提供的域名记录是“授权的”。同样,由 ICANN 授权的顶级域名管理机构以及它们授权的机构所属的服务器也是权威的域名服务器。权威域名服务器上的授权记录是由管理员通过配置文件设置的,另外,授权域名服务器之间还会定期通过“区域传递”来交换这些记录以保持持续的更新。

一次典型的域名解析是解析器首先向根域名服务器发起请求,请求查询被解析域名所在的顶级域名的信息。根域名服务器通常会返回所有该顶级域名的域名服务器的名称,解析器再向顶级域名所有者服务器发起解析,此时可能收到解析的结果,也可能收到下一个域名服务器的名称。如果是后者,则解析器再次向下一级域名服务器发起请求,直到得到它想要的结果。下面是用 dig 命令跟踪解析域名 work.luodichen.com 的 IP 地址的结果。

MacBook-Air-luodichen:~ luodichen$ dig +trace work.luodichen.com

; <<>> DiG 9.8.3-P1 <<>> +trace work.luodichen.com
;; global options: +cmd
.                       408915  IN      NS      k.root-servers.net.
.                       408915  IN      NS      c.root-servers.net.
.                       408915  IN      NS      l.root-servers.net.
.                       408915  IN      NS      g.root-servers.net.
.                       408915  IN      NS      d.root-servers.net.
.                       408915  IN      NS      f.root-servers.net.
.                       408915  IN      NS      b.root-servers.net.
.                       408915  IN      NS      h.root-servers.net.
.                       408915  IN      NS      i.root-servers.net.
.                       408915  IN      NS      a.root-servers.net.
.                       408915  IN      NS      m.root-servers.net.
.                       408915  IN      NS      e.root-servers.net.
.                       408915  IN      NS      j.root-servers.net.
;; Received 228 bytes from 202.96.128.86#53(202.96.128.86) in 392 ms

com.                    172800  IN      NS      l.gtld-servers.net.
com.                    172800  IN      NS      c.gtld-servers.net.
com.                    172800  IN      NS      e.gtld-servers.net.
com.                    172800  IN      NS      b.gtld-servers.net.
com.                    172800  IN      NS      i.gtld-servers.net.
com.                    172800  IN      NS      j.gtld-servers.net.
com.                    172800  IN      NS      g.gtld-servers.net.
com.                    172800  IN      NS      h.gtld-servers.net.
com.                    172800  IN      NS      k.gtld-servers.net.
com.                    172800  IN      NS      a.gtld-servers.net.
com.                    172800  IN      NS      d.gtld-servers.net.
com.                    172800  IN      NS      m.gtld-servers.net.
com.                    172800  IN      NS      f.gtld-servers.net.
;; Received 508 bytes from 192.36.148.17#53(192.36.148.17) in 413 ms

luodichen.com.          172800  IN      NS      f1g1ns1.dnspod.net.
luodichen.com.          172800  IN      NS      f1g1ns2.dnspod.net.
;; Received 250 bytes from 192.41.162.30#53(192.41.162.30) in 390 ms

work.luodichen.com.     600     IN      NS      ns1.oray.net.
work.luodichen.com.     600     IN      NS      ns2.oray.net.
;; Received 88 bytes from 112.90.82.194#53(112.90.82.194) in 87 ms

work.luodichen.com.     60      IN      A       113.76.146.88
;; Received 52 bytes from 61.174.40.200#53(61.174.40.200) in 81 ms

可以看到在解析 work.luodichen.com 的过程中,经历了如下几个阶段

  1. 向本地配置的 DNS 服务器 202.96.128.86 查询根域名 . 的域名服务器,得到 13 个根域名服务器的域名;
  2. 向其中某个根域名服务器 192.36.148.17 查询顶级域名 com 的域名服务器,得到一些服务器列表;
  3. 向其中某个 com 域名服务器查询 luodichen.com 的域名服务器,得到 f1g1ns1.dnspod.net 和 f1g1ns2.dnspod.net 两个域名服务器的域名;
  4. 向其中某个 luodichen.com 的域名服务器查询 work.luodichen.com 的域名服务器,得到 ns1.oray.net 和 ns2.oray.net 两个域名服务器的域名;
  5. 向其中某个 work.luodichen.com 的域名服务器查询 work.luodichen.com 的 IP 地址,得到最终结果是 113.76.146.88。

在实际的终端应用程序中,可能并不需要像以上的实验那样从根服务器开始一级一级地发起查询请求。如果所有的终端应用程序都这样做,一方面根域名服务器将承担巨大的网络压力;另一方面一次域名解析可能耗费非常长的时间,影响效率。解决这个问题的是缓存(Cache)技术。

除根域名之外的一些域名服务器,它们除了运行着域名服务程序之外,还运行着域名解析器。当这些服务器收到一个不属于它管辖的区域的域名解析请求时,它会尝试以客户端的身份向别的域名服务器发起解析请求,并将最终的解析结果返回给它的客户端,这种服务器称作递归域名服务器,它的客户端发起的解析请求称为递归解析请求。这种服务器同时还可能存在着一个高速缓存(Cache),用来缓存上面提到的这些域名解析的结果,当下次又有相同的域名的请求时,服务器会直接将缓存中的记录返回给客户端,并标记这个记录是“非权威的(non-authoritative)”查询结果。为了确保缓存中的信息能及时更新,每条 DNS 记录都有对应的存活时间(TTL, time to live),当缓存中的信息存在的时间超过它的 TTL 时,这条缓存记录就会过期失效,下次请求这条记录时,服务器又会以递归查询的方式解析这个域名,并再次存入缓存中。

为了解决 DNS 查询效率的问题,通常我们在终端系统中配置的是从 ISP 处获取的 DNS 服务器地址或者一些商业 DNS 服务器地址,如 114.114.114.114、8.8.8.8 等。这些服务器都属于带有缓存的递归服务器,终端解析器只要向这些服务器发送一次递归查询请求就能很快地得到查询结果。

解析器通过 DNS 协议向域名服务器发起查询请求,关于 DNS 协议的细节,以及域名系统多个资源记录作用与格式将在下一篇博文中讨论。

(允许转载本文,转载请注明出处:http://luodichen.com/blog/?p=318 )

参考文献
[1] P. Mockapetris, DOMAIN NAMES – CONCEPTS AND FACILITIES, RFC 1034, November 1987; www.ietf.org/rfc/rfc1034.txt
[2] P. Mockapetris, DOMAIN NAMES – IMPLEMENTATION AND SPECIFICATION, RFC 1035, November 1987; www.ietf.org/rfc/rfc1035.txt
[3] W. Richard Stevens, TCP/IP 详解 卷1:协议[M]. 机械工业出版社, 2000.