Automated Test Case Generation

http://jaygarl291.springnote.com

Tao Xie 홈피에서 퍼옴..

레벨 1. timeline을 스스로 제시하고, 이를 잘 지킨다.

레벨 2. timeline을 스스로 제시하나 자주 실패하거나 늘어진다.

레벨 3. 스스로 제시하는 timeline은 없지만 이에 대해 스스로 지도교수와 논하려 애쓴ㄷ.ㅏ

레벨 4. 지도교수에게 찾아오지도 않으며, 응답도 없다.


나는 그나마 레벨 2인듯.

Weakest precondition이란?
다익스트라가 언급.

post-assertion을 봤을때, 무엇이 이 assertion을 true로 만드는 weakest condition이냐?
다시 말해 assertion을 true만들기위해 무조건 true야 하는 것들은 무엇이냐?

[WP ^ [test&action] ] -> Assertion

Weakest란 뜻은 A=>B는 되고, B=>A는 안될때 B는 weaker than A, A는 stronger than B.
가장 weakest한 possible predicate는 "true". 왜냐하면 A=> true는 A가 무엇이든간에 true이기 때문.
반대로 strong guest possible precdicate은 false.
A => false 무엇이든간에 항상 false.

다음과 같은 statement를 생각해보자

x = F(S);
S는 모든 프로그램 변수를 갖는 state vector이다.
이 statement는 "all action"이므로 test는 true가 된다.

만약 P(x)가 true가 실행후 true가 된다고 하면, 실행 전에는 무엇이 true인가?
답은 wp(x = F(S);, P) = P(F(S))

예제:
wp (x=5, y > x) = y > 5  
x = 5 이후에 y > x가 되려면 그 전에는 y > 5이어야 한다.

문제:
wp(x=x+y;, y>x) = ?
wp(y=2*y;, y<5) = ?
wp(y=2*y;, even(y)) = ?

답
y > x+y
y < 5/2
even(2*y)

(그냥 대입하면 된다)

WP Convention
WP expression에 logic simplification을 적용하는게 일반적.
예: even(2*y)는 true로 simplify되고
i + 1<= n 은 i < n으로 simplify된다.

Predicate Transformers
앞에서 본 것처럼 post-condition을 weakest pre-condition으로 변환하는 것을 "predicate transformer"라고 한다.
a predicate은 단지 a set of states이기 때문에, WP는 the set of state after를 a statement to a set before로 변환하는 것이다.



To be continued.



참고 : http://www.cs.umd.edu/~mvz/handouts/weakest-precondition.pdf (wp.pdf)
http://en.wikipedia.org/wiki/Predicate_transformer_semantics

class_atdg.pdf

이 논문은 스웨덴의 Jon Edvardsson이 1999년에 발표한 서베이 논문이다.

전반적으로 당시의 자동 테스트 데이터 생성에 관한 연구를 잘 나열하였고, 쉽게 읽힌다.
이 논문에서는 자동화 테스트 데이터 생성중  프로그램에 기반한 생성이을 다룬다.
소프트웨 테스팅은 전체 소프트웨어의 50%를 차지할 만큼 비중이 크다.
1996년에 1996 Ferguson and Korel이 테스트 데이터 생성을 다음의  세가지로 나누었다.
random, path-oriented, and goal-oriented test

-기본 컨셉
A typical system consists of "program analyzer, path selector and test data generator."
The paths are then given as argument to the test data generator which derives input values that exercise the given paths.
information concerning infeasible paths.

A control flowgraph. G=(N, E, s, e) node, edge, start, end
node는 basic block으로 정의됨.
edge는 branch predicate로 label됨.
A path is a sequence of nodes p = <p1, p2, ..pqp>

feasible path - 닿을 수 있음
infeasible path - 닿을 수 없음
어떤 input x에 대해 path p가 infesible하다면, path p is relatively infeasible for input x

-테스트 데이터 제너레이터
프로그램 애널라이져 = dependency graph나 control flow 그래프를 제공한다.
두가지 방법으로 인풋을 찾음
First find the path predicate for the path. Second, solve the path predicate in terms of input variables.
서치 메소드의 예: alternating variable, simulated annealing, and dierent heuristics based on equation rewriting
systems
테스트 제너레이터의 세가지 방법 : random, goal-oriented, and path oriented
각각은 static or dynamic.

1. symbolic execution은 plenty of computer resources를 필요, e.g. expressions have to be resolved
and transformed.
게다가 소스 코드 없는 함수 콜에 대해서는 알 수 없는 것과 같은 제약사항이 있음
그리고, symbolic executor 자체를 만드는데 노력이 듦.
하지만 violation을 체크할 필요가 없다는 장점이 있음.

2.random testing 은 간단하다. 실제로 string, collection 등 모두 a stream of bits이기때문이다. 하지만, it merely relies on probability it has quite low chances infinding semantically small faults,

3.goal oriented testing은 a set of paths에 대한 guidance를 제공한다. path의 처음부터끝까지 traverse하는게 아니라 그 안에 있는 unspecific 패쓰에 대한 해결을 찾는다. chaining 어프로치와그에 대한 확장인 assertion-oriented 어프로치가 있다.
chaining approach: data dependency를 따진다.이 체인은 실행되는 동안 생성이 된다.
assertion-oriented approach: assert을 자동이나 수동으로 넣어 assert이 violated되지 않도록 확인한다.

4. path-oriented approach는 constraint based test data generation 메소드 제안. (offutt)


패스 셀렉터
the path-prefix strategy introduced by Prather and Myers [12] that ensures branch coverage modulo (relatively) infeasible paths.

따올만한 문장
Dueto the complexity of the generation problem a great deal of the workhas been based on toy programs, i.e. programs that either are veryshort in length, low in complexity, or lack the use of many standardlanguage features such as abstract data types and pointers. Hence, notresembling anything that is developed for instance in industry.

문제점
Array and pointers : indexing problem, shape problem
Objects: dynamically allocated 되기 때문에 어려움
Loops: input variable에 의존. loop의 고정회수가 중요. 그리고 symbolic evaluation a closed form of
the loop must be derived.
Module: 함수처리를 어떻게 할 것인가? 함수를 전부 inline으로 박아버리던가, 함수 안의 것을 먼저 처리하던가..
InfeasiblePaths: undecidable. If the system is linear we can by Gaussianelimination conclude whether that path is feasible [7]. For non-linearsystems it becomes more inconvenient.
Constraint Satisfaction:  path predicate or branch predicate을 풀기위해 some constraint를 만족시켜야됨. Because
of function calls all constraints cannot be solved in symbolicexecution.The dynamic approaches do not suffer from function calls tothe same extent, but there will still be constraints to satisfy.
Oracle: 테스트 케이스가 성공하는지 실패하는지 판단하는 오라클을 갖는다면 이상적인 테스트가 될 것이다. 하지만 이럴려면 소스코드와 함께 요구사항을 명세하여야 한다.

결론:
다음과 같은 연구가 필요하다.
Constraint-satisfaction techniques
 Object-oriented programs
 Pointers and shapes
 Assertions
 Modules
 Path selection
 Data and control dependency
 Oracle problem

우리는 다들 최초의 컴퓨터가 애니악이라고 알고 있다. 하지만, 최초의 컴퓨터는 Iowa State University의 아타나소프(Atanasoff) 교수와 그 학생인 베리(Berry)가 만든 ABC (Atanasoff Berry Computer)이다. 이는 에니악 보다 수년전에 만들어졌으며, 아타나소프가 에니악의 개발자 Mauchly에게 이 아이디어를 주어서 애니악이 개발되었다고도 한다.

이 이야기는 이미 70년대에 특허 소송으로 아타나소프의 Computer가 최초라는 것이 밝혀졌다..머 글구, 아이오와 주립대는...최초의 팩시밀리라든가 최초의 우라늄 농축..으로도 유명하다.