นักพัฒนา C++ เผชิญกับความท้าทายที่น่าประหลาดใจเมื่อพยายามเริ่มต้นตัวสร้างตัวเลขสุ่มอย่างถูกต้อง แม้ว่าจะใช้เครื่องมือในตัวของ standard library แล้วก็ตาม ในขณะที่ภาษาอย่าง Python และ JavaScript จัดการการ seeding แบบสุ่มโดยอัตโนมัติผ่าน entropy ของระบบปฏิบัติการ C++ กลับต้องการการตั้งค่าด้วยตนเองซึ่งมักนำไปสู่ปัญหาที่ละเอียดอ่อนแต่ร้ายแรง
ปัญหาการ Seeding ด้วยจำนวนเต็มตัวเดียว
นักพัฒนาหลายคนใช้รูปแบบทั่วไปที่ดูเหมือนสมเหตุสมผลแต่สร้างข้อบกพร่องร้ายแรง พวกเขาดึงตัวเลข 32 บิตหนึ่งตัวจากอุปกรณ์สุ่มของระบบและใช้มันเพื่อ seed ตัวสร้าง Mersenne Twister ที่เป็นที่นิยม วิธีการนี้จำกัดตัวสร้างให้มีสถานะเริ่มต้นที่เป็นไปได้เพียงประมาณ 4 พันล้านสถานะ ทำให้เสี่ยงต่อการโจมตีแบบ brute-force
ชุมชนได้รับรู้ว่านี่เป็นปัญหาที่แพร่หลาย นักพัฒนาคนหนึ่งได้แบ่งปันวิธีแก้ปัญหาที่แข็งแกร่งกว่าโดยสร้างจำนวนเต็มสุ่ม 624 ตัวเพื่อเติมสถานะภายในของ Mersenne Twister อย่างเหมาะสม ให้ entropy เต็ม 19,937 บิตที่ตัวสร้างต้องการ อย่างไรก็ตาม แม้แต่วิธีการนี้ยังเผชิญกับความซับซ้อนเนื่องจากวิธีการทำงานของระบบ seed sequence ของ C++
ข้อกำหนดสถานะของ Mersenne Twister :
- สถานะภายใน: จำนวนเต็ม 32 บิต จำนวน 624 ตัว (19,937 บิต)
- แนวทางปฏิบัติที่ไม่ดีทั่วไป: การใช้ seed เพียง 32 บิตเดียว (32 บิต)
- แนวทางที่แนะนำ: จำนวนเต็มแบบสุ่ม 624 ตัวจากระบบ entropy
- ช่องโหว่: สถานะที่เป็นไปได้ประมาณ 4 พันล้านสถานะเมื่อใช้การ seeding ด้วยจำนวนเต็มตัวเดียว
ความเอนเอียงของการกระจายสร้างช่องว่างที่ไม่คาดคิด
ปัญหาการ seeding มีมากกว่าความคาดเดาได้ เมื่อใช้ข้อมูล seed ไม่เพียงพอ ตัวเลขบางตัวก็ไม่สามารถปรากฏเป็นผลลัพธ์แรกจากตัวสร้างได้เลย ในการทดสอบ ตัวเลขอย่าง 7 และ 13 ไม่เคยปรากฏขึ้น ในขณะที่ตัวเลขอื่นๆ ปรากฏบ่อยกว่าที่คาดหวังหลายเท่า สิ่งนี้สร้างความเอนเอียงเชิงระบบที่คงอยู่ตลอดการใช้งานตัวสร้างทั้งหมด
สำหรับแอปพลิเคชันที่อาศัยการกระจายแบบสุ่มสม่ำเสมอ ความเอนเอียงนี้อาจสร้างปัญหาจริง แอปมือถือสมมุติที่สุ่มตัวอย่างข้อมูลผู้ใช้อาจพบว่าเกณฑ์ความน่าจะเป็นบางอย่างไม่เคยถูกกระตุ้น นำไปสู่ข้อมูลที่หายไปหรือผลลัพธ์ที่เบี้ยว
Seed sequence หมายถึงอัลกอริทึมที่แปลงข้อมูล seed เป็นสถานะภายในของตัวสร้าง
ความไม่สอดคล้องข้ามแพลตฟอร์มเพิ่มความซับซ้อน
นักพัฒนายังรายงานความแตกต่างข้ามแพลตฟอร์มที่น่าหงุดหงิด โค้ด seeding เดียวกันสามารถสร้างลำดับสุ่มที่แตกต่างกันบน Linux เทียบกับ Windows แม้จะใช้คอมไพเลอร์และตรรกะเดียวกัน สิ่งนี้เกิดขึ้นเพราะการใช้งานอุปกรณ์สุ่มพื้นฐานแตกต่างกันระหว่างระบบปฏิบัติการ ทำให้ยากต่อการสร้างการทดสอบที่ทำซ้ำได้หรือพฤติกรรมที่สอดคล้องกันข้ามแพลตฟอร์ม
ปัญหาการ Seed แบบข้ามแพลตฟอร์ม:
- พฤติกรรมของ
std::random_deviceแตกต่างกันไปในแต่ละระบบปฏิบัติการ - Linux และ Windows สร้างลำดับที่แตกต่างกันแม้จะใช้โค้ดเดียวกัน
- การใช้งาน entropy จากฮาร์ดแวร์เทียบกับการใช้งานแบบ pseudo-random แตกต่างกันไปตามแพลตฟอร์ม
- วิธีแก้ไข: ใช้ seed ที่กำหนดไว้แน่นอนเพื่อการทดสอบที่สามารถทำซ้ำได้
ชุมชนแสวงหาทางเลือกที่ดีกว่า
การอภิปรายเผยให้เห็นว่านักพัฒนาที่มีประสบการณ์หลายคนหลีกเลี่ยงไลบรารีสุ่มมาตรฐานของ C++ โดยสิ้นเชิง พวกเขาชี้ไปที่ตัวสร้างทางเลือกอย่าง PCG (Permuted Congruential Generator) หรือไลบรารีเฉพาะทางอย่าง random123 ที่เสนอประสิทธิภาพที่ดีกว่า หน่วยความจำที่เล็กกว่า หรือพฤติกรรมที่คาดเดาได้มากกว่า
ไม่มีใครใช้ header เพราะมันถูกสาปและลัทธิความเข้ากันได้แบบย้อนหลังตามปกติรับประกันว่ามันจะยังคงเป็นแบบนั้นต่อไป
นักพัฒนาบางคนชอบเขียนตัวสร้างง่ายๆ ของตัวเองมากกว่าการต่อสู้กับความซับซ้อนของ standard library สำหรับแอปพลิเคชันที่ไม่ต้องการความปลอดภัยเชิงการเข้ารหัส อัลกอริทึมที่ง่ายกว่าอย่าง xorshift128+ มักให้ความสุ่มที่เพียงพอด้วยความยุ่งยากที่น้อยกว่า
เครื่องมือสร้างตัวเลขสุ่มทางเลือกที่กล่าวถึง:
- PCG (Permuted Congruential Generator): มีคุณสมบัติทางคณิตศาสตร์ที่ดีกว่า ถูกนำมาใช้เป็นค่าเริ่มต้นในหลายภาษาโปรแกรม
- random123: ไม่มีสถานะ สามารถทำซ้ำได้ เหมาะสำหรับ GPU
- xorshift128+: เรียบง่าย รวดเร็ว เพียงพอสำหรับการใช้งานที่ไม่ใช่การเข้ารหัส
- mt19937_64: Mersenne Twister แบบ 64-bit เร็วกว่าประมาณ 2 เท่าบนแพลตฟอร์ม 64-bit
เส้นทางข้างหน้า
ปัญหาเกิดจากตัวเลือกการออกแบบของ C++ ที่บังคับให้นักพัฒนาใช้ seed sequence แม้เมื่อทำงานกับข้อมูลสุ่มคุณภาพสูงจากระบบปฏิบัติการ มาตรฐานสามารถปรับปรุงได้โดยอนุญาตการเริ่มต้นโดยตรงจากค่าสุ่มหลายตัวและผ่อนปรนข้อกำหนดปัจจุบันบางประการ
จนกว่าจะถึงเวลานั้น นักพัฒนาต้องเลือกอย่างระมัดระวังระหว่างความสะดวกและความถูกต้อง สำหรับแอปพลิเคชันที่คุณภาพของความสุ่มมีความสำคัญ ความพยายามเพิ่มเติมในการ seed ตัวสร้างอย่างเหมาะสมหรือเปลี่ยนไปใช้ไลบรารีทางเลือกจะคุ้มค่าในการหลีกเลี่ยงบั๊กที่ละเอียดอ่อนและช่องโหว่ด้านความปลอดภัย
อ้างอิง: C++ Seeding Surprises