กราฟการเรียกใช้ฟังก์ชัน การวิเคราะห์ความสัมพันธ์ของโปรแกรม

กราฟการเรียกใช้ฟังก์ชัน (Call Graph หรือ Call Multigraph) คือ กราฟการไหลของการควบคุม (Control-flow graph) ประเภทหนึ่งที่ใช้แสดงความสัมพันธ์ในการเรียกใช้งานระหว่างซับรูทีน (Subroutines) หรือฟังก์ชันต่าง ๆ ภายในโปรแกรมคอมพิวเตอร์ โดยในทางทฤษฎีกราฟ แต่ละโหนด (Node) จะแทนหนึ่งโปรซีเยอร์ (Procedure) และแต่ละเส้นเชื่อม (Edge) จากโหนด f ไปยังโหนด g จะระบุว่าโปรซีเยอร์ f มีการเรียกใช้โปรซีเยอร์ g ซึ่งหากเกิดวงจร (Cycle) ภายในกราฟ จะหมายถึงการเรียกใช้ฟังก์ชันแบบเรียกซ้ำ (Recursive calls)

ประเภทของกราฟการเรียกใช้ฟังก์ชัน

กราฟการเรียกใช้ฟังก์ชันสามารถแบ่งออกเป็นสองประเภทหลักตามวิธีการสร้างและข้อมูลที่นำมาใช้ ดังนี้

1. กราฟการเรียกใช้แบบไดนามิก (Dynamic Call Graph)

คือการบันทึกเหตุการณ์ที่เกิดขึ้นจริงในขณะที่โปรแกรมกำลังทำงาน (Runtime) มักได้มาจากเครื่องมือประเภท โปรไฟล์เลอร์ (Profiler) ข้อดีของกราฟประเภทนี้คือมีความแม่นยำสูงเนื่องจากบันทึกสิ่งที่เกิดขึ้นจริง แต่มีข้อจำกัดคือจะแสดงผลเฉพาะการทำงานในรอบนั้น ๆ (Single run) เท่านั้น ไม่สามารถครอบคลุมทุกกรณีที่เป็นไปได้ของโปรแกรม

2. กราฟการเรียกใช้แบบสแตติก (Static Call Graph)

คือการวิเคราะห์ซอร์สโค้ดเพื่อสร้างกราฟที่แสดงทุกความเป็นไปได้ในการเรียกใช้ฟังก์ชันโดยไม่ต้องรันโปรแกรม อย่างไรก็ตาม การสร้างกราฟแบบสแตติกที่แม่นยำสมบูรณ์เป็นปัญหาที่ตัดสินไม่ได้ (Undecidable problem) ดังนั้น อัลกอริทึมส่วนใหญ่จึงใช้วิธีการประมาณการค่าที่ครอบคลุม (Overapproximation) ซึ่งหมายความว่ากราฟจะแสดงทุกความสัมพันธ์ที่เกิดขึ้นจริง แต่อาจรวมถึงความสัมพันธ์ที่ในทางปฏิบัติจะไม่มีวันเกิดขึ้นจริงด้วย

ระดับความแม่นยำและการวิเคราะห์

ความแม่นยำของกราฟการเรียกใช้ฟังก์ชันขึ้นอยู่กับทรัพยากรที่ใช้ในการคำนวณและหน่วยความจำ โดยแบ่งระดับความละเอียดได้ดังนี้

• แบบไม่คำนึงถึงบริบท (Context-insensitive): เป็นระดับที่แม่นยำน้อยที่สุด โดยจะมีเพียงโหนดเดียวสำหรับแต่ละโปรซีเยอร์ ไม่ว่าฟังก์ชันนั้นจะถูกเรียกจากที่ใดก็ตาม
• แบบคำนึงถึงบริบท (Context-sensitive): มีความแม่นยำสูงกว่า โดยจะแยกโหนดตามบริบทการเรียก (Call stack) ที่ฟังก์ชันนั้นถูกเรียกใช้งาน กราฟประเภทนี้ที่ละเอียดที่สุดเรียกว่า Calling Context Tree ซึ่งมักสร้างได้ง่ายในแบบไดนามิก แต่สร้างได้ยากและใช้เวลานานมากในแบบสแตติกสำหรับโปรแกรมขนาดใหญ่

สำหรับภาษาโปรแกรมที่มีคุณสมบัติการส่งผ่านค่าแบบไดนามิก (Dynamic dispatch) เช่น Java หรือ C++ หรือภาษาที่มีฟังก์ชันเป็นพลวัต (First-class functions) เช่น Python การสร้างกราฟแบบสแตติกที่แม่นยำจำเป็นต้องใช้ผลลัพธ์จากการวิเคราะห์นามแฝง (Alias analysis) ซึ่งในทางกลับกัน การวิเคราะห์นามแฝงที่แม่นยำก็ต้องการกราฟการเรียกใช้ฟังก์ชัน ดังนั้น ระบบวิเคราะห์สแตติกส่วนใหญ่จึงใช้วิธีการคำนวณทั้งสองอย่างไปพร้อม ๆ กัน

ประโยชน์และการประยุกต์ใช้งาน

กราฟการเรียกใช้ฟังก์ชันมีประโยชน์หลากหลายด้านในการพัฒนาซอฟต์แวร์ ได้แก่

• การกำจัดโค้ดที่ไม่ได้ใช้งาน (Dead Code Elimination): ใช้ค้นหาโปรซีเยอร์หรือฟังก์ชันที่ไม่มีการเรียกใช้งานจากส่วนใดของโปรแกรมเลย
• การจัดทำเอกสาร (Documentation): ช่วยให้ผู้พัฒนาเข้าใจโครงสร้างและความซับซ้อนของโปรแกรมได้ง่ายขึ้นผ่านการมองเห็นภาพ (Visualization)
• การตรวจสอบความปลอดภัย: ใช้ตรวจจับความผิดปกติในการทำงานของโปรแกรม หรือตรวจหาการโจมตีประเภทการฉีดโค้ด (Code injection attacks)

เครื่องมือสำหรับสร้างกราฟการเรียกใช้ฟังก์ชัน

เครื่องมือในปัจจุบันแบ่งตามลักษณะการทำงานได้ดังนี้