Call-Graphing Analysis Là Gì?
Phân tích đồ thị gọi hàm – Call-Graphing Analysis là một phương pháp sử dụng trong việc phân tích source code để hiểu cách các hàm hoặc phương thức được gọi và tương tác với nhau trong chương trình. Nó tập trung vào việc xây dựng và mô hình hóa một đồ thị biểu diễn quan hệ giữa các hàm hoặc phương thức.
Call-graphing bao gồm các đỉnh và cạnh:
- Đỉnh (Node): Đại diện cho các hàm hoặc phương thức trong chương trình.
- Cạnh (Edge): Biểu diễn cho việc gọi hoặc kết nối giữa các hàm hoặc phương thức. Một hàm A gọi hàm B sẽ có một cạnh từ A đến B.
Mục Đích Của Việc Sử Dụng Call-Graphing Analysis
Qua việc xây dựng đồ thị này, bạn có thể hiểu rõ hơn về cách các hàm tương tác với nhau trong quá trình thực thi của chương trình. Mục tiêu chính của phân tích đồ thị gọi hàm là:
- Phát hiện gọi hàm và luồng điều khiển: Hiểu quá trình gọi và chuyển đổi giữa các hàm, phân tích các luồng điều khiển trong chương trình.
- Xác định các mối quan hệ và phụ thuộc: Đồ thị gọi hàm giúp xác định các phụ thuộc giữa các hàm, thông qua việc xác định hàm nào gọi đến hàm nào và mối quan hệ giữa chúng.
- Tối ưu hóa và phân tích hiệu suất: Cung cấp thông tin để tối ưu hóa cấu trúc code và hiệu suất chương trình. Ví dụ như xác định các phần code không được sử dụng hoặc tối ưu hóa thứ tự gọi hàm để cải thiện hiệu suất.
Phân tích đồ thị gọi hàm là một công cụ mạnh mẽ trong việc hiểu cấu trúc và tương tác của các hàm hoặc phương thức trong chương trình. Đồng thời cung cấp thông tin quan trọng để tối ưu hóa và cải thiện source code.
Sử Dụng Call-Graphing Analysis Trong Integration Testing
Chúng ta cần bao nhiêu trường hợp thử nghiệm để thực hiện thử nghiệm tích hợp? Các phương pháp quản lý kiểm thử tốt là gì? Khả năng ước tính số lượng tài nguyên? Khi xem xét unit test, chúng ta phát hiện ra rằng độ phức tạp theo chu kỳ (cyclomatic complexity) của McCabe ít nhất có thể cung cấp cho chúng ta bộ cơ sở – số lượng trường hợp thử nghiệm tối thiểu mà chúng ta cần.
Phương pháp tiếp cận vị từ thiết kế của McCabe, bao gồm ba bước:
- Bước 1: Vẽ biểu đồ cuộc gọi giữa các module của một hệ thống cho thấy cách mỗi unit gọi và được gọi bởi các unit khác. Biểu đồ này có bốn loại tương tác riêng biệt, như bạn sẽ thấy sau đây.
- Bước 2: Tính độ phức tạp tích phân.
- Bước 3: Chọn các bài kiểm tra để thực hiện từng loại tương tác, không phải mọi sự kết hợp của tất cả các tương tác.
Giống như unit test, điều này không chỉ cho chúng ta cách kiểm tra toàn diện tất cả các đường dẫn có thể có trong hệ thống. Mà nó còn cung cấp cho chúng ta số lượng thử nghiệm tối thiểu mà chúng ta cần để bao quát cấu trúc của hệ thống.
Chúng ta sẽ sử dụng thuật ngữ đường dẫn cơ bản/kiểm thử cơ bản để mô tả các kiểm thử này.
Lệnh Gọi Vô Điều Kiện
Hình 1: Uncondition call
Đầu tiên là một lệnh gọi vô điều kiện. Như được hiển thị ở đây, nó được chỉ định bằng một mũi tên đường thẳng giữa hai module. Vì không bao giờ có quyết định với lệnh gọi vô điều kiện nên độ phức tạp không tăng lên do nó. Điều này được biểu thị bằng số 0 được đặt ở phía nguồn của mũi tên kết nối các module.
Hãy nhớ rằng, chính những quyết định sẽ làm tăng độ phức tạp. Chúng ta đi đâu? Chúng ta làm điều đó bao nhiêu lần? Trong cuộc gọi vô điều kiện, không có quyết định nào được đưa ra. Nó luôn luôn xảy ra.
Điều quan trọng là phải phân biệt kiểm thử tích hợp với chức năng của các module mà chúng ta đang kiểm tra. Hoạt động bên trong của một module có thể cực kỳ phức tạp với tất cả các loại tính toán đang diễn ra. Đối với kiểm thử tích hợp, tất cả những điều đó đều bị bỏ qua; chúng ta quan tâm đến việc thử nghiệm cách các module giao tiếp và làm việc cùng nhau
Lệnh Gọi Có Điều Kiện
Hình 2: Conditional call
Chúng ta có thể quyết định gọi một module khác hoặc có thể không. Hình 2 hiển thị cuộc gọi có điều kiện, trong đó quyết định nội bộ được đưa ra về việc liệu chúng ta có gọi unit thứ hai hay không. Một lần nữa, đối với thử nghiệm tích hợp, chúng ta không quan tâm đến việc đưa ra quyết định như thế nào. Bởi vì chỉ có khả năng một cuộc gọi có thể được thực hiện nên chúng ta nói rằng độ phức tạp tăng lên một. Lưu ý rằng mũi tên hiện có một chấm tròn nhỏ được điền đầy ở nguồn. Một lần nữa, chúng ta thể hiện mức độ phức tạp tăng lên bằng cách đặt số 1 ở đuôi mũi tên.
Xin lưu ý, sự phức tạp không phải là một, nó là sự gia tăng của một. Giả sử biểu đồ này đại diện cho toàn bộ hệ thống. Chúng ta có sự gia tăng độ phức tạp của một, nhưng câu hỏi là sự gia tăng từ cái gì?
Một cách để xem xét vấn đề này là nói rằng thử nghiệm đầu tiên là miễn phí. Vì vậy, lệnh gọi vô điều kiện không làm tăng độ phức tạp và chúng ta sẽ cần một thử nghiệm để giải quyết nó. Một bài kiểm tra là mức tối thiểu. Bạn có bao giờ cảm thấy thoải mái khi kiểm tra 0 lần không?
Trong trường hợp này, chúng ta bắt đầu với thử nghiệm đầu tiên đó. Sau đó, vì chúng ta tăng một unit nên chúng ta sẽ cần thử nghiệm thứ hai. Như bạn có thể mong đợi, một thử nghiệm là nơi chúng ta gọi module, thử nghiệm còn lại là khi chúng ta không gọi.
Lệnh Gọi Có Điều Kiện Loại Trừ Lẫn Nhau
Hình 3: Mutually exclusive conditional call
Tiếp theo, chúng ta sẽ xem xét đến lệnh gọi có điều kiện loại trừ lẫn nhau – mutually exclusive conditional call. Điều này xảy ra khi một module sẽ gọi một và chỉ một trong số nhiều unit khác nhau. Chúng ta đảm bảo sẽ thực hiện cuộc gọi đến một trong các unit; cái nào sẽ được gọi sẽ được quyết định bởi một số logic bên trong module.
Trong cấu trúc này, rõ ràng là chúng ta sẽ cần kiểm tra tất cả các cuộc gọi có thể xảy ra vào lúc này hay lúc khác. Điều đó có nghĩa là sẽ có sự gia tăng phức tạp. Sự gia tăng độ phức tạp này có thể được tính toán dựa trên số lượng mục tiêu có thể có. Nếu có ba mục tiêu như được hiển thị, mức tăng độ phức tạp sẽ là 2, được tính bằng số khả năng trừ đi một. Lưu ý trong biểu đồ rằng một chấm tròn đầy ở đuôi mũi tên cho thấy một số mục tiêu sẽ không được gọi.
Những Lệnh Gọi Không Điều Kiện
Hình 4: Uncontionall calls
Trong biểu đồ tiếp theo (hình 4), chúng ta hiển thị một số thứ trông gần giống nhau. Tuy nhiên, điều quan trọng là phải thấy sự khác biệt. Không có dấu chấm ở đuôi thì không có điều kiện. Điều đó có nghĩa là việc thực hiện bất kỳ thử nghiệm nào phải bao gồm thực thi Unit 0→ Unit 1, Unit 0 → Unit 2 và Unit 0 → n vào lúc này hay lúc khác. Điều này sẽ trông rõ ràng hơn nhiều nếu nó được vẽ bằng ba mũi tên, mỗi mũi tên chạm vào Unit 0 ở những nơi khác nhau thay vì hội tụ về một nơi. Tuy nhiên, dù được vẽ như thế nào thì ý nghĩa vẫn như nhau. Không có dấu chấm có điều kiện, chúng là các kết nối vô điều kiện, do đó độ phức tạp không tăng lên.
Lệnh Gọi Lặp Lại
Hình 5: Iterative call
Trong (hình 5), chúng ta có lệnh gọi lặp lại – iterative call. Điều này xảy ra khi một unit được gọi ít nhất một lần nhưng có thể được gọi nhiều lần. Điều này được biểu thị bằng mũi tên phóng điện trên module nguồn trong biểu đồ. Trong trường hợp này, mức độ phức tạp tăng lên được coi là một, như thể hiện trong biểu đồ.
Lệnh Gọi Có Điều Kiện Lặp Lại
Hình 6: Iterative conditional call
Cuối cùng nhưng không kém phần quan trọng, chúng ta có lệnh gọi có điều kiện lặp lại – iterative conditional call. Như đã thấy trong biểu đồ cuối cùng này (hình 6), nếu chúng ta thêm ký hiệu có điều kiện vào lệnh gọi lặp, nó sẽ tăng độ phức tạp lên một. Điều đó có nghĩa là Unit 0 có thể gọi Unit 1 0 lần, 1 lần hoặc nhiều lần. Về cơ bản, điều này nên được coi là giống hệt như cách chúng ta xử lý phạm vi vòng lặp ở phần trước của chương.
Ví Dụ Về Call-graphing Analysis
Cùng mình xem xét một ví dụ về đoạn code chuyển đổi hex cơ bản.
jmp_buf sjbuf;
long int hexnum;
unsigned long int nhex;
main()
/* Classify and count input chars */
{
int c, qotnum;
void pophdigit();
hexnum = nhex = 0;
if (signal(SIGINT, SIG_IGN) != SIG_IGN) {
signal(SIGINT, pophdigit);
setjmp(sjbuf);
}
while ((c = getchar()) !=EOF) {
switch (c) {
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
/* Convert a decimal digit */
nhex++;
hexnum *= 0X10;
hexnum += (c – '0');
break;
case 'a': case 'b': case 'c':
case 'd': case 'e': case 'f':
/* Convert a lower case hex digit */
nhex++;
hexnum *= 0X10;
hexnum += (c – 'a' + 0xa);
break;
case 'A': case 'B': case 'C':
case 'D': case 'E': case 'F':
/* Convert an upper case hex digit */
nhex++;
hexnum *= 0X10;
hexnum += (c – 'A' + 0xA);
break;
default;
/* Skip any non-hex characters */
break;
}
}
if (nhex == 0) {
fprintf(stderr, "hexcvt: no hex digits to convert!\\n");
} else {
printf("Got %d hex digits: %x\\n", nhex, hexnum);
}
return 0;
}
void pophdigit()
/* Pop the last hex input out of hexnum if interrupted */ {
signal(SIGINT, pophdigit);
hexnum /= 0x10;
nhex --;
longjmp(sjbuf, 0);
}
Đoạn code này dành cho UNIX hoặc Linux; nó sẽ không hoạt động với Windows nếu không sửa đổi cách xử lý ngắt. Đoạn code này có ý nghĩa như sau:
Khi chương trình được gọi, nó sẽ gọi hàm signal(). Nếu giá trị trả về cho main() biết rằng SIGINT hiện không bị bỏ qua, thì main() gọi lại signal() để đặt hàm pophdigit() làm bộ xử lý tín hiệu cho SIGINT.
main() sau đó gọi setjmp() để lưu điều kiện chương trình với dự đoán longjmp() quay lại vị trí này. Lưu ý rằng khi chúng ta sẵn sàng vẽ biểu đồ này, signal() chắc chắn được gọi một lần. Sau đó, nó có thể được gọi lại hoặc không để đặt giá trị trả về.
main() sau đó gọi getchar() ít nhất một lần. Nếu trong lần gọi đầu tiên, EOF được trả về, vòng lặp sẽ bị bỏ qua và fprint() được gọi để báo lỗi. Nếu không phải EOF, vòng lặp sẽ được thực thi. Tất cả các ký tự hex hợp pháp (A–F, a–f, 0–9) sẽ được dịch sang chữ số hex và được thêm vào số hex làm chữ số logic tiếp theo. Ngoài ra, bộ đếm sẽ được tăng lên cho mỗi ký tự hex nhận được. Điều này tiếp tục nhận các ký tự đầu vào cho đến khi tìm thấy EOF.
Nếu nhận được một ngắt (Ctrl-C), nó sẽ gọi thủ tục pophdigit(), thủ tục này sẽ loại bỏ giá trị mới nhất và giảm số lượng chữ số hex.
Để kiểm tra đoạn code này, chúng ta cần tìm số lượng tối thiểu các bài kiểm thử cần trong kiểm thử tích hợp
Hình: Biểu đồ cuộc gọi cho code chuyển đổi hex
Hãy đi qua nó từ trái sang phải.
Tín hiệu cuộc gọi chính của module (A) (B) một lần và có khả năng thực hiện cuộc gọi thứ hai. Điều đó làm cho nó lặp đi lặp lại, với độ phức tạp tăng lên 1.
Hàm pophdigit() (C) có thể được gọi bao nhiêu lần cũng được; mỗi khi có tín hiệu (Ctrl-C), hàm này sẽ được gọi. Khi được gọi, nó luôn gọi hàm tín hiệu (B). Vì nó có thể được gọi là 0 lần, 1 lần hoặc nhiều lần nên độ phức tạp tăng lên là 2.
Hàm setjmp (E) có thể xuất hiện một lần trong trường hợp tín hiệu (B) được gọi hai lần. Điều đó làm cho nó có điều kiện với độ phức tạp tăng lên 1.
Hàm getchar (F) được đảm bảo sẽ được gọi một lần và có thể được gọi bao nhiêu lần cũng được. Điều đó làm cho nó lặp đi lặp lại với độ phức tạp tăng lên 1.
Một trong các hàm printf (G) hoặc fprintf (H) sẽ được gọi nhưng hàm kia thì không. Điều đó làm cho nó trở thành một cuộc gọi có điều kiện loại trừ lẫn nhau. Vì có hai khả năng nên độ phức tạp tăng lên là (N – 1) hoặc 1.
Cuối cùng, hàm pophdigit (C) luôn gọi tín hiệu (B) và longjmp (D), do đó, mỗi tín hiệu đó có độ phức tạp tăng thêm 0.
Do đó:
Integration Complexity = Sum(Design Predicates) + 1
hay IC = (1+2+1+1+1+0+0) + 1 = 7
Độ phức tạp tích hợp là bảy, vì vậy chúng ta cần bảy trường hợp thử nghiệm riêng biệt, phải không? Không cần thiết! Nó đơn giản có nghĩa là có bảy con đường riêng biệt cần phải đi qua. Nếu điều đó nghe có vẻ khó hiểu thì biểu đồ này khác với biểu đồ có hướng mà chúng ta đã sử dụng khi xem xét độ phức tạp chu kỳ. Khi sử dụng biểu đồ cuộc gọi, bạn phải nhớ rằng sau khi cuộc gọi hoàn thành, luồng thực thi sẽ quay trở lại module gọi.
Vì vậy, khi bắt đầu, chúng ta đang thực thi trong main(). Chúng ta gọi hàm signal() và hàm này sẽ quay trở lại hàm main(). Tùy thuộc vào giá trị trả về, chúng ta có thể gọi lại signal() để thiết lập trình xử lý và sau đó quay lại main(). Sau đó, nếu chúng ta gọi signal(), thì lần thứ hai chúng ta gọi setjmp() và quay lại main(). Đây không phải là đồ thị có hướng, trong đó bạn chỉ đi theo một hướng và không bao giờ quay lại vị trí cũ trừ khi có một vòng lặp.
Bài viết về Call-Graphing Analysis hôm nay xin dừng lại tại đây. Cám ơn bạn đã đón xem, hẹn gặp các bạn trong các bài viết tiếp theo.
Happy Testing!