ĐẠi học quốc gia hà NỘi trưỜng đẠi học công nghệ Trần Bình Dương sinh ca kiểm thử tham số HÓa cho chưƠng trình java khóa luận tốt nghiệP ĐẠi học hệ chính quy ngành: Công Nghệ Thông Tin
Chương 2: Sinh dữ liệu kiểm thử tự động cho PUT
tải về 446.91 Kb.
|
- Điều hướng trang này:
- 2.1. Thực thi tượng trưng
- 2.1.2. Thực thi tượng trưng tĩnh
- 2.1.3. Thực thi tượng trưng động
Chương 2: Sinh dữ liệu kiểm thử tự động cho PUTTrong kiểm thử phần mềm, các ca kiểm thử thường được tạo ra thủ công do đó gây tốn kém trong chi phí phát triển phần mềm và làm kéo dài thời gian để hoàn thành một phần mềm. Có các phương pháp khác nhau hỗ trợ việc sinh tự động các ca kiểm thử một cách có hệ thống giúp giảm chi phí cho việc kiểm thử phần mềm. Một trong những phương pháp đơn giản nhất để sinh tự động các ca kiểm thử đó là kiểm thử ngẫu nhiên (random testing)[5]. Với kiểm thử ngẫu nhiên các đầu vào cho hệ thống được sinh ngẫu nhiên. Để thực hiện, một luồng các bits được sinh ngẫu nhiên để thể hiện cho các giá trị của tham số đầu vào. Giả sử với một hàm nhận tham số đầu vào có kiểu string thì chỉ cần sinh ngẫu nhiên một luồng các bits để thể hiện giá trị cho một chuỗi. Kiểm thử ngẫu nhiên có ưu điểm là dễ dàng sinh các đầu vào ngẫu nhiên và hệ thống kiểm thử ngẫu nhiên không yêu cầu nhiều tài nguyên bộ nhớ lúc thực thi. Nhưng hạn chế của nó là kiểm tra cùng một hành vị thực thi của chương trình nhiều lần với những đầu vào khác nhau và chỉ có thể kiểm tra được một số trường hợp thực thi của chương trình. Thêm vào đó, kiểm thử ngẫu nhiên khó xác định được khi nào việc kiểm thử nên được dừng lại và nó không biết tại điểm nào không gian trạng thái đã được thám hiểm hết. Để xác định khi nào việc kiểm thử dừng lại thì hệ thống kiểm thử ngẫu nhiên được kết hợp với các adequacy criterion [5]. Giả sử adequacy criterion là bao phủ lệnh (statement coverage)[5] thì việc kiểm thử chỉ dừng lại khi tất cả các câu lệnh của chương trình được thực thi ít nhất một lần. Một phương pháp khác đang rất phổ biến giúp khắc phục được hạn chế của kiểm thử ngẫu nhiên đó là thực thi tượng trưng[6]. Thực thi tượng trưng chính là việc xây dựng các ràng buộc dựa vào các giá trị tượng trưng và giải quyết các ràng buộc đó để sinh ra các giá trị làm đầu vào chương trình mà có thể thực thi chương trình theo các đường đi thực thi khác nhau. Ý tưởng chính của thực thi tượng trưng đó là thực thi một chương trình với những giá trị tượng trưng. Có hai cách tiếp cận đối với thực thi tượng trưng đó là cách tiếp cận dựa trên phân tích tĩnh và phân tích động chương trình. Việc lựa chọn các đầu vào kiểm thử cho PUT liên quan tới vấn đề sinh dữ liệu kiểm thử tự động. Sinh dữ liệu kiểm thử tự động là một lĩnh vực nghiên cứu rất rộng trong kiểm thử phần mềm. Có rất nhiều các kỹ thuật khác nhau[8, 10, 18] được sử dụng để sinh dữ liệu kiểm thử tự động. Tuy nhiên với PUT thì các dữ liệu làm đầu vào kiểm thử cần được chọn lựa làm sao để PUT có thể kiểm tra được sự thực thi của chương trình theo tất cả các đường đi có thể. Hơn nữa số lượng các đầu vào kiểm thử cho PUT là tối thiểu. Việc sinh dữ liệu để có thể kiểm tra được sự thực thi một chương trình theo tất cả các đường đi có thể với các dữ liệu đó là một vấn đề phức tạp và không phải lúc nào cũng thực hiện được trên thực tế. Thực chất của vấn đề sinh dữ liệu kiểm thử tự động cho PUT là việc xây dựng ràng buộc và xử lý ràng buộc. Các ràng buộc được xây dựng sao cho chúng có thể biểu thị cho các đường đi thực thi trong một chương trình. Và giải quyết các ràng buộc đó sẽ sinh ra các dữ liệu mà chương trình có thể thực thi với các dữ liệu đó để đi theo các đường đi khác nhau trong chương trình. 2.1. Thực thi tượng trưng2.1.1. Những khái niệm cơ bảnMột chương trình P có thể xem xét như một hàm, P : S→ R , trong đó S là tập hợp các đầu vào (input) có thể và R là tập hợp các đầu ra (output) có thể. S có thể được biểu diễn bởi vector I=(x1,…,xk,…,xn), trong đó xk là tham số đầu vào thứ k của P với k N. Một bộ giá trị i=(d1,...,dk,…,dn) biểu thị cho một đầu vào của P, i S, trong đó dk là các giá trị cụ thể sao cho dk Dxk với Dxk là miền giá trị của tham số đầu vào xk. Sự thực thi của chương trình P với đầu vào i S được biểu thị bởi P(i). Biểu đồ luồng điều khiển (CFG) của một chương trình P là một bộ G=(N, E, s, e), trong đó G là một đồ thị có hướng, với N là tập hợp các nút (node), E = {(n,m) | n,m N} là tập hợp các cạnh, s là nút vào và e là nút ra, s và e là duy nhất. Mỗi nút được định nghĩa như một khối cơ bản (basic block) là một dãy liên tục các chỉ thị(câu lệnh) sao cho luồng điều khiển khi đi vào nút và ra khỏi nút không bị ngưng lại (halt). Điều này có nghĩa là nếu bất cứ câu lệnh nào của block được thực thi thì toàn bộ block được thực thi. Mỗi cạnh của CFG nối 2 nút với nhau và được gán nhãn với một biểu thức điều kiện rẽ nhánh. Nếu cạnh không được gán nhãn có nghĩa là điều kiện luôn đúng. Một đường đi (path) cụ thể là dãy các nút: p=(p1, p2,…,pn) với pn là nút cuối của đường đi p và (pi,pi+1) E (1 < i < n-1). Nếu tồn tại i S sao cho sự thực thi P(i) đi theo đường đi p thì p gọi là đường đi khả thi, ngược lại p là đường đi không khả thi. Một đường đi bắt đầu tại nút vào và kết thúc tại nút ra gọi là đường đi đầy đủ, nếu kết thúc tại nút không phải là nút ra thì gọi là đường đi không đầy đủ (path segment). Một chương trình P cũng có thể xem gồm tập hợp các câu lệnh (statements) là thành phần nhỏ nhất trong một chương trình mà có thể được thực thi riêng rẽ. Bằng việc thực thi một câu lệnh chương trình có thể chuyển đổi trạng thái thực thi của nó từ trạng thái hiện thời tới trạng thái mới. Một đường đi thực thi của chương trình P là một dãy các câu lệnh mà có thể được thực thi theo thứ tự từ điểm bắt đầu của chương trình. Đoạn đường đi đầu tiên (path prefix) có độ dài n của đường đi thực thi p là một dãy bao gồm n câu lệnh đầu tiên của p. Do đó việc sinh dữ liệu kiểm thử cho PUT là việc sinh một tập hợp tối thiểu các đầu vào i Є S sao cho có thể thực thi tất cả các đường đi trong CFG của chương trình được PUT kiểm thử.
Với mỗi tham số đầu vào một giá trị tượng trưng được đưa ra để kết hợp với nó. Mỗi biến trong chương trình P mà giá trị của nó phụ thuộc vào giá trị của các tham số đầu vào thì trong quá trình thực thi tượng trưng một giá trị tượng trưng sẽ được tính toán để kết hợp cùng với nó. Mỗi giá trị tượng trưng biểu thị cho một tập hợp các giá trị cụ thể mà một biến hoặc một tham số đầu vào có thể nhận. Kết quả trả về của một chương trình được thực thi tương trưng nếu có cũng được biểu thị bởi biểu thức của các giá trị tượng trưng. Giá trị tượng trưng của biến x có thể được biểu thị bởi: (a). Một ký hiệu đầu vào(input symbol). (b). Một biểu thức kết hợp giữa các giá trị tượng trưng bởi các toán tử. (c). Một biểu thức kết hợp giữa giá trị tượng trưng và giá trị cụ thể bởi toán tử. Một ký hiệu đầu vào biểu thị cho giá trị tượng trưng của một tham số đầu vào lúc bắt đầu thực thi chương trình. Các tham số đầu vào khác nhau của P được biểu thị bởi các ký hiệu đầu vào khác nhau. Các toán tử (operator) là các phép toán như cộng (+), trừ (), nhân (*), chia (/). Nếu giá trị của một biến x không phụ thuộc vào các giá trị đầu vào thì không có giá trị tượng trưng nào được tính toán để kết hợp với nó. Giá trị tượng trưng cuả các biến và các tham số đầu vào được cập nhật như các giá trị cụ thể của nó trong quá trình thực thi. Gán một giá trị cụ thể từ một biến tới biến khác dẫn đến giá trị tượng trưng cũng được sao chép nếu biến được gán tới một biến khác có một giá trị tượng trưng. Giả sử với một câu lệnh gán x=e, nếu e là một tham số đầu vào, thì giá trị tượng trưng được gán cho x sẽ có dạng (a). Nếu e là một biểu thức tính toán gồm các toán hạng. Các toán hạng đó có thể là biến, tham số đầu vào hoặc hằng thì giá trị tượng trưng của biến x sẽ là một biểu thức tượng trưng dạng (b) nếu mỗi toán hạng trong biểu thức có một giá trị tượng trưng kết hợp với nó, hoặc là một biểu thức tượng trưng dạng (c) nếu có toán hạng là hằng số hoặc không có giá trị tượng trưng kết hợp với nó. Giá trị cụ thể của một hằng hoặc một biến cũng được sử dụng trong biểu thức tượng trưng nếu như hằng hoặc biến đó không có giá trị tượng trưng kết hợp với nó. Trạng thái của một chương trình được thực thi tương trưng bao gồm các giá trị của các biến trong chương trình, điều kiện đường đi (PC) và biến đếm chương trình (program counter). Biến đếm chương trình xác định chỉ thị (câu lệnh) tiếp theo sẽ được thực thi. Mỗi PC là một biểu thức kết hợp bởi các ràng buộc mà các giá trị đầu vào chương trình cần thỏa mãn để chương trình được thực thi theo đường đi tương ứng với PC đó. Mỗi ràng buộc là một biểu thức tượng trưng dạng x o y trong đó x là giá trị tượng trưng, y là giá trị tượng trưng hoặc giá trị cụ thể và o {≤, ≠, =, <, >, ≥}. Các ràng buộc đó chính là biểu thức của điều kiện rẽ nhánh và biểu thức phủ định của điều kiện rẽ nhánh tương ứng với nhánh true và nhánh false. Tại mỗi câu lệnh rẽ nhánh, các ràng buộc được tạo ra. Các ràng buộc này được biểu thị bởi biểu thức của các giá trị tượng trưng hay biểu thức của giá trị tượng trưng và giá trị cụ thể phụ thuộc vào biến xuất hiện trong biểu thức điều kiện của câu lệnh rẽ nhánh có giá trị tượng trưng được tính toán để kết hợp với nó hay không. Trong quá trình thực thi tượng trưng, việc chương trình được thực thi theo một đường đi cụ thể nào đó không phụ thuộc vào các giá trị cụ thể của các biến và các tham số đầu vào. Tại các điểm rẽ nhánh, cả hai nhánh ra sẽ được xem xét để điều hướng sự thực thi hiện thời đi theo. SE chủ yếu liên quan tới việc thực thi hai loại câu lệnh đó là câu lệnh gán (assignment statments) và câu lệnh rẽ nhánh. Tại các câu lệnh gán thì giá trị tượng trưng của các biến chương trình cũng như các tham số đầu vào có liên quan tới câu lệnh gán đó được cập nhật. Tại các câu lệnh rẽ nhánh, chương trình sẽ được điều hướng để thực thi theo cả hai nhánh. Và hai ràng buộc đường đi tương ứng với hai nhánh sẽ được tạo ra. Một ràng buộc là biểu thức điều kiện tại câu lệnh rẽ nhánh. Còn ràng buộc kia là phủ định của biểu thức điều kiện rẽ nhánh. Các ràng buộc này sẽ được cập nhật vào điều kiện đường đi tương ứng với các nhánh đó. Đồng thời các PC này sẽ được đánh giá để xác định đường đi tương ứng với PC đó có khả thi. Nếu PC được đánh giá trở thành false thì SE sẽ quay lui và chỉ thực thi theo nhánh khả thi. Các PC được tạo ra bằng cách thu gom các ràng buộc trên các đường đi tương ứng và giải quyết các ràng buộc này sẽ sinh ra các giá trị cụ thể cho các tham số đầu vào. Để mô tả sự thực thi tượng trưng một chương trình. Một cây thực thi tượng trưng (SET) được đưa ra để biểu thị cho các đường đi thực thi trong quá trình thực thi tượng trưng một chương trình. Các nút biểu thị cho các trạng thái của chương trình được thực thi tượng trưng và các cạnh biểu thị cho sự chuyển đổi trạng thái từ trạng thái này sang trạng thái khác. Ví dụ 2.1: public void Swap(int x, int y){ 1: if (x > y) { 2: x = x + y; 3: y = x - y; 4: x = x - y; 5: if (x - y > 0) 6: assert(false); }
Hình 2 : Cây thực thi tượng trưng Cây thực thi tượng trưng (Hình 2) biểu thị cho việc thực thi tượng trưng hàm Swap. Bắt đầu thực thi tượng trưng hàm Swap bằng cách gán giá trị tượng trưng cho các tham số đầu vào x và y lần lượt là X và Y, đồng thời khởi tạo PC là true. Tới câu lệnh rẽ nhánh 1, cả hai nhánh đi của chương trình đều chọn để thực thi với các giá trị tượng trưng. Tại câu lệnh này, biểu thức điều kiện rẽ nhánh và biểu thức phủ định của điều kiện rẽ nhánh được thêm vào PC theo các nhánh tương ứng. Trong thực thi tượng trưng, nếu điều kiện rẽ nhánh được thêm vào PC thì PC đó tương ứng với PC của nhánh mà điều kiện rẽ nhánh nhận giá trị true. Sau khi thực thi câu lệnh 1, hàm Swap tiếp tục được thực thi theo nhánh mà điều kiện rẽ nhánh ở câu lệnh 1 nhận giá trị true. Khi thực thi các câu lệnh gán 2, 3, 4 thì giá trị của các biến được cập nhật với giá trị mới. Khi tới câu lệnh rẽ nhánh 5, thêm 2 nhánh đi mới được xem xét để thực thi với các giá trị tượng trưng. PC tiếp tục được cập nhật theo các nhánh tương ứng. Tại đây, PC được cập nhật với điều kiện rẽ nhánh ở 5 trở thành false do không tồn tại bộ giá trị nào thỏa mãn PC. Vì vậy hàm Swap chỉ thực thi theo nhánh mà PC được cập nhật với biểu thức phủ định của điều kiện rẽ nhánh tại 5. Và câu lệnh 6 sẽ không bao giờ được thực thi. Tại mỗi điểm rẽ nhánh, PC được cập nhật và một bộ xử lý ràng buộc được sử dụng để xác định nhánh tương ứng với PC đó có khả thi hay không để điều hướng việc thực thi hiện thời đi theo nhánh đó . Nếu PC được đánh giá tới false thì SE sẽ quay lui và chỉ thực thi chương trình theo nhánh mà PC được đánh giá tới true. 2.1.3. Thực thi tượng trưng độngThực thi tượng trưng động[14, 25] là kỹ thuật thực thi tương trưng dựa trên phân tích chương trình động. Thực thi tượng trưng động chính là sự kết hợp giữa thực thi cụ thể và thực thi tượng trưng. Trong thực thi tượng trưng động, chương trình được thực thi nhiều lần với những giá trị khác nhau của tham số đầu vào. Bắt đầu bằng việc chọn những giá trị tùy ý cho các tham số đầu vào và thực thi chương trình với những giá trị cụ thể đó. Với những giá trị cụ thể này thì chương trình sẽ được thực thi theo một đường đi xác định. Thực thi chương trình với các giá trị cụ thể của tham số đầu vào và thu gom các ràng buộc trong quá trình thực thi theo đường đi mà sự thực thi cụ thể này đi theo, đồng thời suy ra các ràng buộc mới từ những ràng buộc đã thu gom được. Tại các câu lệnh rẽ nhánh, biểu thức điều kiện rẽ nhánh sẽ được đánh giá phụ thuộc vào các giá trị cụ thể của các tham số đầu vào. Nếu biểu thức điều kiện rẽ nhánh nhận giá trị là True thì biểu thức của điều kiện rẽ nhánh sẽ được thu gom vào ràng buộc của PC và được ghi nhớ, đồng thời phủ định của điều kiện rẽ nhánh sẽ được sinh ra và được thêm vào một PC tương ứng với nhánh còn lại mà sự thực thi cụ thể đó không đi theo. Một bộ xử lý ràng buộc (Constraint Solver) sẽ được sử dụng để giải quyết các ràng buộc mới sinh ra này để sinh ra các giá trị cụ thể của tham số đầu vào. Ngược lại, nếu là False thì biểu thức phủ định của điều kiện rẽ nhánh sẽ được thu gom vào ràng buộc của PC tương ứng với nhánh đi mà sự thực thi hiện thời đang đi theo và được ghi nhớ. Đồng thời điều kiện rẽ nhánh sẽ được sinh ra và thêm vào PC tương ứng với nhánh đi còn lại mà sự thực thi hiện thời không đi theo. Các giá trị mới được sinh ra của các tham số đầu vào sẽ tiếp tục được thực thi và quá trình này sẽ được lặp lại cho tới khi chương trình được thực thi theo tất cả các đường đi. Do các chương trình được thực thi với những giá trị cụ thể nên có thể thấy rằng tất cả các đường đi phân tích được trong quá trình thực thi tượng trưng động đều là các đường đi khả thi. Thuật toán 2.1: DSE S : Tập hợp tất cả các câu lệnh của chương trình P S : Tập con của S (s I : Tập hợp các đầu vào của P P(i): Thực thi chương trình với đầu vào i I, sao cho s được thực thi J : Tập hợp các đầu vào của P được thực thi (J={i | P(i)}) C(i): Ràng buộc thu gom được từ việc thực thi P(i), hay còn gọi là điều kiện đường đi C’(i): Điều kiện đường đi suy ra từ C(i) Bước 0: J:= {} (tập rỗng) Bước 1: Chọn đầu vào i không thuộc J (dừng lại nếu không có i nào được tìm ra) Bước 2: Output i Bước 3: Thực thi P(i); ghi nhớ điều kiện đường đi C(i), suy ra C’(i) Bước 4: Đặt J := J Bước 5: Quay lại bước 1 Ví dụ 2.2: 0:void DSE(int[] a) 1:{ 2: if (a == null) return; 3: if (a.length > 0) 4: if (a[0] == 123456789) 5: throw new Exception("bug"); 6:}
Solve (c): Biểu thị cho việc xử lý ràng buộc c. Hàm DSE bắt đầu được thực thi với giá trị tùy ý của tham số đầu vào. Giá trị tùy ý này thường được chọn là giá trị mặc định tương ứng với kiểu của tham số đầu vào. Ở đây giá trị null được chọn, sau đó thực thi hàm DSE với giá trị null này. Khi tới câu lệnh rẽ nhánh 2, điều kiện a==null được thỏa mãn do đó ràng buộc C(i):(a==null) được ghi nhớ. Ràng buộc C’(i) được suy ra bằng cách lấy phủ định của điều kiện rẽ nhánh, C’(i): (a!=null). Solve (C’(i)) suy ra được a={}. Tiếp tục thực thi chương trình với giá trị a={}. Với a={} khi tới câu lệnh rẽ nhánh 3, biểu thức a.length > 0 nhận giá trị false, ràng buộc C(i): (a!=null) && !(a.length >0) được ghi nhớ. Ràng buộc C’(i):(a!=null && a.length > 0) được sinh ra, solve (C’(i)) ta được giá trị mới của tham số đầu vào là {0}. Tiếp tục thực thi hàm DSE với giá trị a={0}. Với giá trị a={0} khi đi tới câu lệnh rẽ nhánh 4, thì biểu thức điều kiện rẽ nhánh nhận giá trị false đo đó ràng buộc C’(i):( a!=null && a.length>0 && a[0]!=123456789) được ghi nhớ. Điều kiện C’(i): (a!=null && a.length>0 && a[0]==123456789) được sinh ra, solve (C’(i)) ta được giá trị a={12345678}. Đến đây thì không còn đường đi nào của hàm DSE mà chưa được thực thi và qua trình thực thi sẽ được dừng lại. Bảng 1: Ví dụ về thực thi tượng trưng động
Một số hệ thống sinh kiểm thử tự động cài đặt DSE bằng cách khởi tạo một cây thực thi tương trưng để biểu thị các đường đi thực thi khác nhau. Nếu như có thể xây dựng được một cây thực thi tượng trưng đầy đủ thì có thể sinh ra các giá trị đầu vào sao cho có thể đạt được sự bao phủ luồng điều khiển (CFG coverage)[5] ở mức cao. Với những hệ thống này, mã nguồn chương trình cần được sửa đổi để cho phép thực thi tượng trưng được thực hiện dọc theo việc thực thi cụ thể. Chương trình được thực thi với những giá trị ngẫu nhiên với một chiều sâu (depth) định trước của SET. Chiều sâu được sử dụng để giúp cho việc thực thi một chương trình được dừng lại trong trường hợp chương trình có vòng lặp vô tận hoặc các hàm đệ quy. Khi chương trình bắt đầu được thực thi thì một cây thực thi tương trưng tương ứng cũng được khởi tạo. Trong quá trình thực thi, các giá trị tượng trưng của các biến sẽ đươc tính toán và các ràng buộc đường đi sẽ được sinh ra từ các giá trị tượng trưng đó. Với mỗi ràng buộc được sinh ra thì SET sẽ được thêm vào một đỉnh (node) tương ứng với ràng buộc đó. Việc xây dựng SET tiến hành trong suốt quá trình thực thi. Có thể xem mỗi lần thực thi là mỗi lần duyệt một đường đi của SET. Khi các câu lệnh rẽ nhánh được thực thi, các đường đi trong SET cũng được mở rộng theo các nhánh đó. Với những giá trị cụ thể việc thực thi sẽ đi theo một nhánh cụ thể. Nhánh còn lại mà sự thực thi cụ thể đó không đi theo sẽ có một đỉnh mới được tạo ra và được đánh dấu là chưa được thăm. Đỉnh mới được tạo ra sẽ lưu các ràng buộc tương ứng với nhánh mà đỉnh đó được thêm vào. Sau mỗi lần thực thi, một đỉnh mà chưa được thăm trong SET sẽ được chọn và ràng buộc đường đi tương ứng với đoạn đường đi từ đỉnh gốc (root) của SET tới đỉnh được chọn đó sẽ được thu gom và ràng buộc đường đi này sẽ được đưa tới một bộ xử lý ràng buộc (Constraint Solver) để xử lý. Nếu ràng buộc đường đi này không thỏa mãn, một đỉnh khác của SET mà chưa được thăm sẽ được chọn, còn nếu ràng buộc đường đi này thỏa mãn thì bộ xử lý ràng buộc sẽ sinh ra các giá trị đầu vào cụ thể cho lần thực thi tiếp theo. Khi các đỉnh tương ứng với các nhánh trong SET đều được thăm hết thì thuật toán sẽ tạm dừng (terminate). Và các giá trị đầu vào cụ thể được sinh ra cùng với những thông tin phân tích được trong mỗi lần thực thi (method summary) sẽ được sử dụng để sinh ra các UT và cho mục đích báo cáo. Các giá trị đầu vào cụ thể được trả về sau mỗi lần chạy được kết hợp với các thông tin về lỗi phát hiện được nếu lần thực thi đó chương trình ngưng lại vì một ngoại lệ chưa được xử lý, hoặc vì một lỗi nào đó. Ví dụ 2.3: Thực thi tượng trưng với phương thức nhận đầu vào là đối tượng Ta xét một phương thức nhận 2 tham số đầu vào, một tham số là đối tượng SimpleList và một tham số có kiểu int: Class SimpleList {
.../* other methods */ }
2: x=x+5; 3: if(x > 0) 4: o.value=x; 5: else 6: o=null; 7: if(o.next==o) 8: error(); 9:}
Với những phương thức nhận tham số đầu vào có kiểu đối tượng thì kỹ thuật khởi tạo lười[29] được sử dụng trong việc thực thi tượng trưng phương thức đó. Giả sử các giá trị ngẫu nhiên được chọn là x=-10, o=null. Các giá trị tượng trưng được gán tương ứng tới các tham số đầu vào cùng với những giá trị cụ thể được chọn ở trên. S(x)=sym, R(o)=obj1. Thực thi chương trình với giá trị của các tham số đầu vào được chọn ngẫu nhiên này. Sau khi thực thi câu lệnh 2, giá trị tượng trưng của x là S(x)=sym+5, giá trị cụ thể của nó cũng được tính toán (x = -5). Tới câu lệnh rẽ nhánh 3, với giá trị x= -5 thì điều kiện rẽ nhánh được đánh giá tới false. Ràng buộc S(x)=sym+5 <= 0 lưu vào đỉnh tương ứng của SET cho nhánh mà sự thực thi cụ thể đi theo và được đánh dấu là đã được thăm, đồng thời một đỉnh mới đại diện cho nhánh còn lại được tạo ra và ràng buộc sym+5 > 0 được lưu vào đỉnh này, đỉnh mới được tạo ra được đánh dấu là chưa được thăm. Đến câu lệnh 7 thì một ngoại lệ NullPointerException được ném ra và việc thực thi sẽ dừng lại. Cây thực thi tượng trưng được xây dựng tương ứng với lần chạy này (Hình 3(a)). Đỉnh mới được tạo ra của SET mà chưa được thăm được chọn để thu gom ràng buộc trên nhánh tương ứng với đỉnh chưa được thăm đó. Ràng buộc thu gom được là sym+5 > 0. Giải quyết ràng buộc này ta được một giá trị cụ thể của x giả sử là x=0. Do không có ràng buộc liên quan tới đối tượng l được tạo ra nên giá trị của nó sẽ được khởi tạo với phương thức khởi tạo mặc định cho lần thực thi tiếp theo. Sau khi khởi tạo đối tượng o và giải quyết ràng buộc, chương trình tiếp tục được thực thi với các giá trị đầu vào mới này đó là x=0, o=new simpleList(). Đỉnh chưa được thăm tương ứng với nhánh thực thi này tạo ra từ lần thực thi trước trong SET sẽ được chọn để mở rộng. Đến câu lệnh 4, trường value của đối tượng o được truy cập lần đầu tiên. Một giá trị tượng trưng sẽ được kết hợp với nó, và giá trị tượng trưng này được cập nhật do giá trị của trường đó được gán với giá trị của biến x. Tới câu lệnh 7, một đối tượng o.next sẽ được khởi tạo lười với một giá trị cụ thể và một giá trị tượng trưng kết hợp với nó, o.next=new simpleList(), R(o.next)=obj2. Tại câu lệnh rẽ nhánh này, 2 ràng buộc tương ứng với 2 nhánh được tạo ra obj1=obj2, và obj1≠obj2. Ràng buộc obj1≠obj2 tương ứng với nhánh mà sự thực thi cụ thể hiện thời đang đi theo. Với ràng buộc obj1=obj2 thì một đỉnh mới được tạo ra tương ứng với nhánh mà sự thực thi cụ thể hiện thời không đi theo để lưu ràng buộc obj1=obj2 và đỉnh mới này được đánh dấu là chưa được thăm. Cây thực thi tượng trưng tương ứng với lần thực thi này được biểu thị trong Hình 3(b). Sau khi lần chạy này kết thúc đỉnh mới được tạo ra này lại được chọn để mở rộng và ràng buộc thu gom được trên đường đi chứa đỉnh này là S(x)=sym+5 > 0 && obj1=obj2 && S(o.value)= sym+5. Ràng buộc đối tượng obj1=obj2 được giải quyết bằng phép gán tham chiếu giữa 2 đối tượng mà các giá trị tượng trưng này đại diện, o.next=o. Đối tượng o lúc này được khởi tạo và giá trị của trường value được gán với giá trị sinh ra từ việc giải quyết ràng buộc. Cây thực thi tương trưng tương ứng với lần thực thi chương trình với các giá trị đầu vào mới sinh ra này được biểu thị trong Hình 3(c).
Hình 3: Cây thực thi tượng trưng được quản lý riêng Каталог: jspui -> bitstream -> 123456789 123456789 -> Nguyễn Ngọc Lý Giám đốc Trung tâm Nghiên cứu về Môi trường và Cộng đồng 123456789 -> Vò Quúnh Thu Cao häc K18 123456789 -> Khoa Báo chí Đhkhxh&NV 123456789 -> Acknowledgements 123456789 -> Danh mục chữ viết tắT 123456789 -> Chương TỔng quan vật liệu mao quản trung bình (mqtb) trật tự 1 Giới thiệu chung 123456789 -> Khoa hóa họC (141 142 báo cáo) tải về 446.91 Kb. Chia sẻ với bạn bè của bạn:
|
S)
i
