การตรวจจับข้อผิดพลาด — checksum ที่จงใจให้อ่อน

บทความก่อนหน้าพูดถึง checksum มาแล้วสี่ครั้ง — Ethernet มีช่องตรวจท้ายเฟรม IP มี checksum ที่คุ้มเฉพาะส่วนหัว TCP และ UDP มี checksum ที่คุ้มทั้งเซกเมนต์ และ บทเรื่องชั้น ใช้ checksum ของ TCP เป็นหลักฐาน ว่าชั้นรั่ว

แต่ยังไม่มีบทไหนตอบคำถามที่ควรถามก่อน — มันจับอะไรได้จริง และจับอะไรไม่ได้

คำตอบสั้น ๆ คือ checksum ของอินเทอร์เน็ตอ่อนกว่าที่คนคิดมาก มันจับความ เสียหายบางแบบไม่ได้เลย ไม่ใช่บางครั้ง แต่ไม่ได้เลย ทุกครั้ง และนั่นไม่ใช่ บั๊ก มันคือผลของคุณสมบัติที่เอกสารออกแบบเมื่อปี 1978 ลิสต์ไว้เป็นข้อดี

บทความนี้จะพิสูจน์ด้วยการรันจริงสองแสนครั้ง

ถ้ายังไม่เคยดู เริ่มตรงนี้

checksum ของอินเทอร์เน็ตคำนวณเองได้ในไม่กี่บรรทัด ไม่ต้องมีไลบรารีอะไร

$ python3 -c "
import struct
def ck(b):
    if len(b)%2: b += b'\0'
    s = sum(struct.unpack('!%dH' % (len(b)//2), b))
    while s >> 16: s = (s & 0xffff) + (s >> 16)
    return (~s) & 0xffff
print(hex(ck(b'HELLO WORLD!')))"

ได้ 0x2e91 — จับกลุ่มไบต์ทีละสองไบต์ บวกกันทั้งหมด เอาตัวทดวนกลับมาบวก ซ้ำ แล้วกลับบิตทั้งหมด จบ

ความเรียบง่ายนี้คือทั้งจุดแข็งและจุดอ่อนของมัน

ความเสียหายเกิดได้หลายแบบ ไม่ใช่แบบเดียว

เวลาพูดถึงข้อมูลเสีย คนมักนึกถึงบิตเดียวที่พลิก แต่บนสายจริงความเสียหาย มีหลายรูปแบบ และแต่ละแบบท้าทายวิธีตรวจต่างกัน

  single-bit    บิตเดียวพลิก
  burst         บิตติดกันหลายตัวเสียพร้อมกัน เพราะสัญญาณรบกวนชั่วขณะ
  reorder       ข้อมูลมาถึงสลับลำดับ
  duplicate     ข้อมูลชิ้นเดิมมาถึงสองครั้ง
  truncate      ข้อมูลขาดหาย

วิธีตรวจที่ดีกับแบบหนึ่งอาจใช้ไม่ได้เลยกับอีกแบบ ซึ่งเป็นประเด็นทั้งหมด ของบทความนี้

parity — ง่ายที่สุด และพังง่ายที่สุด

วิธีที่เก่าที่สุดคือนับจำนวนบิตหนึ่ง แล้วเติมอีกหนึ่งบิตให้จำนวนรวมเป็นเลขคู่ ปลายทางนับใหม่ ถ้าไม่เป็นคู่แปลว่าเสีย

ข้อจำกัดของมันตามมาจากนิยามตรง ๆ — มันจับได้เฉพาะเมื่อจำนวนบิตที่พลิก เป็นเลขคี่ พลิกสองบิต จำนวนรวมกลับมาเป็นคู่ และ parity บอกว่าปกติดี

ผมรันจริงสองแสนครั้ง

  flip 1 bit    จับได้ทุกครั้ง
  flip 2 bits   จับไม่ได้เลยสักครั้ง
  flip 3 bits   จับได้ทุกครั้ง
  flip 4 bits   จับไม่ได้เลยสักครั้ง

ไม่ใช่ 99% หรือ 1% แต่เป็น 0% กับ 100% สลับกันไปตามคู่หรือคี่ ซึ่งเป็น พฤติกรรมที่ทำนายได้สมบูรณ์ และแย่มากถ้าความเสียหายจริงมักมาเป็นชุด

checksum ของอินเทอร์เน็ต

RFC 1071 เดือนกันยายน 1988 ชื่อ Computing the Internet Checksum อธิบายวิธี คิดและเหตุผลเบื้องหลัง มันใช้การบวกแบบคอมพลีเมนต์หนึ่ง ซึ่งต่างจากการบวก ธรรมดาตรงที่ตัวทดถูกวนกลับมาบวกที่บิตต่ำสุด

เอกสารอธิบายว่าทำไมถึงเลือกแบบนี้แทน XOR

"One's complement arithmetic is better than two's complement because it is equally sensitive to errors in all bit positions."

"It is just this property that makes some sort of addition preferable to a simple exclusive-OR which is frequently used but permits an even number of drops (pick ups) in any bit channel."

XOR มีปัญหาเดียวกับ parity คือความเสียหายที่เป็นเลขคู่หักล้างกันเอง การบวก แก้ปัญหานั้นได้ แต่แลกมาด้วยปัญหาใหม่

คุณสมบัติสี่ข้อ ที่ข้อแรกคือจุดอ่อน

ภาคผนวกของ RFC 1071 คือเอกสารเก่ากว่านั้นชื่อ IEN 45 ลงวันที่ 5 มิถุนายน 1978 เขียนโดย William W. Plummer ซึ่งลิสต์คุณสมบัติที่ตัวดำเนินการบวกต้องมี ไว้สี่ข้อ ข้อแรกคือ

"(P1) + is commutative. Thus, the order in which the 16-bit bytes are 'added' together is unimportant."

อ่านอีกรอบช้า ๆ ลำดับของเวิร์ดไม่สำคัญ — เขียนไว้ในฐานะข้อดี เพราะทำให้ ผู้ผลิตเลือกอ่านหน่วยความจำทางไหนก็ได้ ทำให้คำนวณได้เร็วบนเครื่องหลายแบบ

แต่ประโยคเดียวกันนั้นมีความหมายอีกอย่าง — ถ้าลำดับไม่สำคัญต่อการคำนวณ การสลับลำดับก็ตรวจไม่ได้

ข้ออื่นตามมาด้วยเหตุผลแบบเดียวกัน

  P2   มีสมาชิกเอกลักษณ์ ผู้ส่งใส่ศูนย์ในช่องแล้วคำนวณได้เลย
  P3   มีตัวผกผัน ผู้รับคำนวณแล้วคาดหวังผลเป็นศูนย์ได้
  P4   มีสมบัติการเปลี่ยนหมู่ ช่อง checksum วางตรงไหนก็ได้

ทั้งสี่ข้อรวมกันทำให้ checksum เร็วและยืดหยุ่นมาก และทำให้มันตาบอดหลายจุด พร้อมกัน

ทดลอง — อะไรจับได้ อะไรจับไม่ได้

ผมเอาข้อความหนึ่งประโยคมาทำให้เสียสี่แบบ แล้ววัดว่าทั้งสามวิธีจับได้ไหม ok คือจับได้ ส่วน MISS คือจับไม่ได้

  corruption                 parity  checksum  CRC-32
  flip 1 bit                 ok      ok        ok
  flip 2 bits in one byte    MISS    ok        ok
  swap two 16-bit words      MISS    MISS      ok
  swap word 1 and word 5     MISS    MISS      ok

สองแถวล่างคือผลของ P1 โดยตรง

ลองนึกถึงความหมายในทางปฏิบัติ ถ้าข้อความคือคำสั่งโอนเงินที่มีเลขบัญชี และจำนวนเงินอยู่คนละเวิร์ด การสลับสองเวิร์ดนั้นเปลี่ยนความหมายทั้งหมด แต่ checksum ยังบอกว่าปกติดีทุกครั้ง

3.1% ที่ไม่ใช่ความบังเอิญ

รันจริงสองแสนครั้งบนข้อความสุ่มยาว 64 ไบต์ นับเฉพาะครั้งที่ตรวจไม่พบ

  corruption       parity            checksum         CRC-32
  flip 1 bit             0 (  0.0%)       0 (  0.0%)        0
  flip 2 bits      200,000 (100.0%)   6,282 (  3.1%)        0
  flip 3 bits            0 (  0.0%)     590 (  0.3%)        0
  flip 4 bits      200,000 (100.0%)     651 (  0.3%)        0
  swap two words   199,995 (100.0%) 199,995 (100.0%)        0

ตัวเลข 3.1% ตรงแถวพลิกสองบิตน่าสนใจที่สุด เพราะถ้าความเสียหายกระจายแบบสุ่ม ล้วน checksum 16 บิตควรพลาดราว 1 ใน 65,536 หรือ 0.0015% สิ่งที่วัดได้ แย่กว่าค่านั้นสองพันเท่า

ผมไล่หากลไก แล้วพบว่ามันอธิบายได้หมด

ถ้าบิตที่พลิกทั้งสองอยู่ตำแหน่งเดียวกันภายในเวิร์ด 16 บิต และพลิก คนละทิศ ตัวหนึ่งจะเพิ่มค่า 2^k อีกตัวจะลดค่า 2^k เท่ากันพอดี ผลรวมไม่เปลี่ยน checksum จึงไม่เปลี่ยน

โอกาสที่จะเป็นแบบนั้นคำนวณได้ตรง ๆ

  1 in 16    ตำแหน่งบิตตรงกัน
  1 in 2     พลิกคนละทิศ
  1 in 32    รวมแล้วเท่ากับ 3.1%

และเมื่อนับจากการทดลอง จำนวนครั้งที่เข้าเงื่อนไขนี้คือ 6,117 ครั้ง ส่วน จำนวนครั้งที่ checksum จับไม่ได้คือ 6,117 ครั้งเท่ากันพอดี ไม่ใช่ใกล้เคียง แต่เท่ากันทุกกรณี

CRC — วิธีที่แข็งกว่า และอยู่ชั้นล่าง

อีเทอร์เน็ตไม่ได้ใช้ checksum แบบบวก มันใช้ CRC-32 ซึ่งคิดจากการหารพหุนาม ในเลขฐานสอง ไม่ใช่การบวก จึงไม่มีคุณสมบัติสลับที่

จากตารางเดียวกัน CRC-32 จับได้ทุกกรณีที่ทดลอง — หนึ่งล้านครั้ง ไม่พลาด สักครั้ง

การที่แต่ละชั้นเลือกวิธีต่างกันไม่ใช่ความไม่ลงรอย แต่เป็นการแลกเปลี่ยนที่ ต่างกัน

  Ethernet   CRC-32       whole frame   ฮาร์ดแวร์คิดให้ ไม่กินซีพียู
  IP         16-bit sum   header only   เราเตอร์ต้องคิดใหม่ทุกฮอป
  TCP        16-bit sum   header+data   ซอฟต์แวร์คิด จึงต้องเร็ว

ทำไมถึงยอมใช้ของอ่อนที่ชั้นบน

คำตอบอยู่ในคุณสมบัติ P2 กับ P4 ที่ยกมาข้างบน — เพราะ เราเตอร์ต้องแก้ ส่วนหัวทุกฮอป

ทุกครั้งที่แพ็กเก็ตผ่านเราเตอร์ ค่า TTL ลดลงหนึ่ง ซึ่งแปลว่า checksum ของ IP ต้องคำนวณใหม่ ถ้าใช้ CRC-32 เราเตอร์จะต้องอ่านทั้งแพ็กเก็ตแล้วคิดใหม่ ทุกครั้ง ในขณะที่การบวกแบบนี้แก้เฉพาะส่วนที่เปลี่ยนได้ โดยไม่ต้องแตะไบต์อื่น

นั่นคือการแลก ความแข็งแรงของการตรวจ กับ ความเร็วในการแก้ระหว่างทาง และตัดสินใจไปตั้งแต่ยุคที่เราเตอร์คือเครื่อง PDP ที่คิดเลขได้ช้ามาก IEN 45 ถึงกับลิสต์จำนวนรอบหน่วยความจำต่อเวิร์ดไว้ในเอกสาร

RFC 1071 ยังระบุคุณสมบัติอีกข้อที่อธิบายว่าทำไมต้องเป็นแบบนี้

"(P6) Adding the checksum to a packet does not change the information bytes."

"This property allows intermediate computers such as gateway machines to act on fields (i.e., the Internet Destination Address) without having to first decode the packet."

เราเตอร์อ่านที่อยู่ปลายทางได้เลยโดยไม่ต้องถอดรหัสอะไรก่อน ซึ่งเป็นสิ่งที่ รหัสแก้ไขข้อผิดพลาดบางชนิดทำไม่ได้

ศูนย์สองตัว และบั๊กที่อยู่ใน RFC สี่ปี

เลขคอมพลีเมนต์หนึ่งมีเรื่องแปลกอยู่อย่างหนึ่ง — มันมีศูนย์สองตัว

  +0   0x0000
  -0   0xFFFF

ทั้งคู่แทนค่าศูนย์ และความแตกต่างนี้ทำให้เกิดบั๊กที่อยู่ในเอกสารมาตรฐาน นานสี่ปี

RFC 1141 ปี 1990 เสนอสูตรลัดให้เราเตอร์แก้ checksum แบบไม่ต้องคำนวณใหม่ ทั้งหมด สูตรนั้นใช้ได้เกือบทุกกรณี ยกเว้นตอนผลลัพธ์เป็นศูนย์ RFC 1624 เดือนพฤษภาคม 1994 จึงออกมาแก้ และอธิบายสาเหตุไว้ว่า

"RFC 1141 yields an updated header checksum of -0 when it should be +0. This is because it assumed that one's complement has a distributive property, which does not hold when the result is 0"

สูตรที่ดูถูกต้องผิดเฉพาะกรณีที่ผลเป็นศูนย์ และไม่มีใครสังเกตอยู่สี่ปี เพราะกรณีนั้นเกิดไม่บ่อย นี่คือลักษณะเฉพาะของบั๊กในเลขคณิต — มันไม่ได้พัง ตลอดเวลา มันรอ

เมื่อมันโกหก

"checksum ผ่าน แปลว่าข้อมูลถูกต้อง" ไม่ใช่ แปลว่าข้อมูลไม่ได้เสียใน รูปแบบที่วิธีนี้จับได้ ซึ่งเป็นคนละเรื่อง

"checksum 16 บิตพลาด 1 ใน 65,536" จริงเฉพาะเมื่อความเสียหายสุ่มล้วน ความเสียหายจริงมีโครงสร้าง และตัวเลขที่วัดได้ข้างบนคือ 3.1% ในบางกรณี

"อีเทอร์เน็ตตรวจแล้ว ชั้นบนไม่ต้องตรวจอีก" CRC ของอีเทอร์เน็ตคุ้มแค่ ช่วงสายเส้นนั้น พอถึงเราเตอร์ เฟรมถูกแกะและประกอบใหม่พร้อม CRC ใหม่ ความเสียหายที่เกิดในหน่วยความจำของเราเตอร์ จะได้ CRC ใหม่ที่ถูกต้อง สำหรับข้อมูลที่ผิดแล้ว นี่คือเหตุผลที่ต้องมี checksum แบบต้นทางถึงปลายทาง อีกชั้น

"CRC คือการเข้ารหัส" ไม่ใช่เลย ใครก็คำนวณ CRC ใหม่ได้ มันตรวจอุบัติเหตุ ไม่ได้ตรวจเจตนา ถ้าต้องกันคนที่ตั้งใจแก้ข้อมูล ต้องใช้ลายเซ็นตามที่ TLS อธิบาย

"checksum ของ UDP ปิดได้ ไม่เป็นไร" บน IPv4 ปิดได้จริง แต่บน IPv6 ปิดไม่ได้ เพราะ IPv6 ตัด checksum ของส่วนหัวออกไปแล้ว ถ้าชั้นขนส่งไม่ตรวจ ก็ไม่เหลือใครตรวจเลย

ตัวอย่างจริงจากงานจริง

กรณีที่ 1 — ข้อมูลเสียแต่ทุกอย่างบอกว่าปกติ

สถานการณ์ ไฟล์ที่คัดลอกผ่านเครือข่ายเสียเป็นครั้งคราว แต่ไม่มีตัวนับ ข้อผิดพลาดที่ไหนขึ้นเลย

อ่านอย่างไร ตัวนับที่สวิตช์นับเฉพาะเฟรมที่ CRC ไม่ผ่าน ถ้าความเสียหาย เกิดในหน่วยความจำของอุปกรณ์กลางทาง ไม่ใช่บนสาย เฟรมจะถูกคำนวณ CRC ใหม่ หลังเสียแล้ว ตัวนับจึงสะอาด และ checksum ของ TCP ก็มีโอกาสพลาดตามตัวเลข ข้างบน วิธีเดียวที่พิสูจน์ได้คือเทียบค่าแฮชของไฟล์ทั้งสองฝั่ง

สิ่งที่ยังไม่ได้พิสูจน์ ค่าแฮชที่ต่างกันบอกว่าข้อมูลเสีย แต่ไม่บอกว่า เสียที่ไหน อาจเป็นดิสก์ หน่วยความจำ หรือเครือข่ายก็ได้ ต้องแยกทดสอบทีละชั้น

กรณีที่ 2 — เลือกวิธีตรวจให้งานของตัวเอง

สถานการณ์ ต้องออกแบบโพรโทคอลของตัวเองสำหรับอุปกรณ์ฝังตัว

อ่านอย่างไร ถามสองคำถามก่อนเลือก

  1  ความเสียหายที่คาดว่าจะเจอเป็นแบบไหน
  2  มีใครต้องแก้ข้อมูลระหว่างทางไหม

ถ้าไม่มีใครแก้ระหว่างทาง ให้เลือก CRC เพราะแข็งกว่ามากและฮาร์ดแวร์ส่วนใหญ่ คิดให้ได้ ถ้ามีอุปกรณ์กลางทางต้องแก้บางฟิลด์ ผลบวกแบบ 16 บิตอาจคุ้มกว่า ด้วยเหตุผลเดียวกับที่ IP เลือกมัน

สิ่งที่ยังไม่ได้พิสูจน์ ตัวเลขในบทความนี้วัดจากความเสียหายที่ผมสร้างขึ้น แบบสุ่ม ความเสียหายบนสายจริงมักมาเป็นชุดติดกัน ซึ่ง CRC ออกแบบมารับมือ โดยเฉพาะ แต่ผมยังไม่ได้ทดลองแบบนั้นในบทความนี้

กรณีที่ 3 — พิสูจน์ว่า checksum ตาบอดจริง

สถานการณ์ ต้องอธิบายให้ทีมเข้าใจว่าทำไมต้องมีแฮชอีกชั้น

คำสั่ง ให้เขารันเอง สิบวินาทีจบ

$ python3 -c "
import struct
def ck(b):
    s = sum(struct.unpack('!%dH' % (len(b)//2), b))
    while s >> 16: s = (s & 0xffff) + (s >> 16)
    return (~s) & 0xffff
a = b'AABB'
b = b'BBAA'
print(a, hex(ck(a)))
print(b, hex(ck(b)))"

เอาต์พุตจริง

  b'AABB' 0x7c7c
  b'BBAA' 0x7c7c

อ่านอย่างไร ข้อมูลคนละชุด ได้ checksum ค่าเดียวกัน เพราะ P1 บอกไว้แล้ว ว่าลำดับไม่สำคัญ การเห็นด้วยตาตัวเองจบการถกเถียงได้เร็วกว่าการอธิบาย

สิ่งที่ยังไม่ได้พิสูจน์ ตัวอย่างนี้แสดงว่ามันเป็นไปได้ ไม่ได้บอกว่าเกิด บ่อยแค่ไหนในเครือข่ายจริง การสลับเวิร์ดต้องมีอะไรบางอย่างทำให้เกิด ซึ่งพบ ได้น้อยกว่าบิตพลิกมาก

เมื่อการตรวจจับไม่พอ

การตรวจจับบอกได้แค่ว่าเสีย ไม่ได้บอกว่าเสียตรงไหนและซ่อมให้ไม่ได้ ทางเลือก มีสองทาง — ขอส่งใหม่ ซึ่งเป็นสิ่งที่ TCP ทำ หรือใส่ข้อมูลซ้ำซ้อนมากพอให้ ปลายทางซ่อมเองได้ ซึ่งเป็นสิ่งที่การสื่อสารดาวเทียมและหน่วยความจำ ECC ทำ

ทางแรกถูกกว่ามากเมื่อส่งใหม่ได้เร็ว ทางที่สองคุ้มกว่าเมื่อการส่งใหม่แพง หรือช้าเกินไป และทั้งสองทางไม่ช่วยอะไรเลยถ้าคนอีกฝั่งตั้งใจแก้ข้อมูล

อ้างอิง

มาตรฐาน

• RFC 1071 กันยายน 1988 Computing the Internet Checksum — วิธีคิด และภาคผนวกที่เป็น IEN 45 ปี 1978 ซึ่งลิสต์คุณสมบัติ P1 ถึง P6 ที่ยกมาอ้างในบทความนี้
• RFC 1141 มกราคม 1990 สูตรลัด สำหรับแก้ checksum ที่มีข้อผิดพลาด
• RFC 1624 พฤษภาคม 1994 ที่แก้ ข้อผิดพลาดนั้น พร้อมคำอธิบายเรื่องศูนย์สองตัว
• RFC 9293 ข้อกำหนดที่ระบุว่า checksum ของ TCP ปิดไม่ได้

อ่านหน้านี้เป็นภาษาอังกฤษ

← กลับไปหน้าความรู้พื้นฐาน