CS 168 · PROJECT 1B · ENGINEERING WORKBOOK
让 Traceroute 经得起真实网络
在 1A 正确路径上加入一条明确的接收验证流水线，处理无关、损坏、截断、丢失、重复、延迟和错误批次响应，而不让修一个测试破坏另一个。
工程合同
- What you build
- 在 1A 正确路径上加入一条明确的接收验证流水线，处理无关、损坏、截断、丢失、重复、延迟和错误批次响应，而不让修一个测试破坏另一个。
- 核心不变量
- 处理任意输入 buffer 要么产生一个属于当前 probe 批次的 responder，要么无副作用地忽略；永不崩溃、永不无限等。
- Definition of Done
- Correct：当前适用测试通过；Understand：能从事件解释状态变化；Evidence：保留最小 trace、失败注入和边界测试。
- 禁止捷径
- 不读取模拟器隐藏全局状态，不修改框架绕过协议，不把本教材伪装成提交实现。
依赖优先的实现路径
1 · 结构合法性
- Build
- 先验证外层 IPv4 最短长度/IHL/Protocol，再验证 ICMP 首部与内嵌原始 IPv4/UDP 长度。任何一步失败都 early return，而不是深层嵌套。
- Evidence
- B2–B8：非法 type/code/protocol、垃圾 payload、截断、无关 UDP、IP options。
2 · 语义相关性
- Build
- 合法 ICMP 仍可能属于别的程序或旧 traceroute。用内嵌原始目的 IP、UDP destination port/probe 标识与当前 TTL/批次关联。
- Evidence
- B16 及无关响应不能污染当前 hop，也不能错误提前终止。
3 · 有界等待
- Build
- 每个 TTL 发固定 probe 数，接收循环既不能为不存在的“额外包”必然超时，也不能因一个 invalid packet 就少等一个有效响应。把“已收 socket 消息数”和“已接受本次响应数”分开。
- Evidence
- B1 无不必要 timeout；B9–B12 在 loop、missing host、silent router、drop 下都终止。
4 · 去重与延迟包
- Build
- 分别去重 responder 与 probe response identity。重复包不应增加计数；延迟副本到下一 TTL 时必须通过内嵌 probe 字段被拒绝。
- Evidence
- B13–B15：duplicate response、duplicate probe、delayed duplicate。
最小 sanity check
先构造只含两个端点和一个可控故障的最小场景。预测每条消息、字段和状态变化，再运行一次；任何额外消息、无法解释的表项或越界状态都视为失败，即使最终输出碰巧正确。
event | pre-state | input fields | expected mutation | emitted output | observed
失败签名
- 为了清空队列写 while recv_select() 导致必然 timeout
- 只按 responder IP 去重而无法区分旧 probe
- 先切片后检查长度
- 为每个 B 测试堆一层特殊分支
Hint 1 · Concept
先指出哪个协议不变量被破坏，不要直接添加特判。
Hint 2 · Structure
让每个输入事件只经过一次“验证 → 状态转移 → 输出”流水线；把可纯计算的部分提取成无副作用函数。
Hint 3 · Debug strategy
对边界前后各造一个输入，用 spy 记录所有发送动作，并在每次 mutation 后断言控制块/表项关系。
完成后的复盘
- 哪个状态是真正的 single source of truth？
- 哪些测试只证明输出，哪些测试能证明没有额外副作用？
- 如果消息延迟、重复、乱序或刚好落在边界，会破坏哪条假设？
- 今天重写时，你会先设计哪三个 helper / invariant？
能力门：不用翻代码，向未来的自己讲清一个正常轨迹、一个失败轨迹和一个恢复轨迹，并能从日志重建状态。
Prediction → Experiment → Evidence
- Predict：为 malformed、unrelated、duplicate、late packet 写预期 branch。
- Experiment：每次只破坏一个长度、protocol、identifier 或 arrival time。
- Evidence：记录 packet 是否被消费、hop set 是否变化、loop 是否继续。
Closed-book reconstruction
为四类异常各写 before/event/after，并解释为什么“收到 packet”不等于“得到本 probe 的证据”。