TELKOM NIKA Indonesia n  Journal of  Electrical En gineering   Vol.12, No.1, Jan uary 20 14 , pp. 818 ~ 8 2 2   DOI: http://dx.doi.org/10.11591/telkomni ka.v12i1.3342            818     Re cei v ed Ma y 27, 201 3; Revi sed Aug u st 10, 2013; Accepted Aug u s t 31, 2013   Study Oftest Data Generation Method Based on  Evolutionary Algorithm      NI Jian, Zha ng Yunlong*   Heb e i Un iversit y  of Eng i ne eri n g, School of Inf o rmatio n  & Ele c tronic Eng i ne erin g   heb ei h and an,  056 03 8   *Corres p o ndi n g  author, em ail :  yun l on gh and an@ 163.com       A b st r a ct   T he study of automatica lly ge nerate test dat a base d  on ev ol uti onary a l g o r ithm  meth od focuses o n   the path cov e rage d i rectio n. T he key  prob le m is how  to construct a suit a b le a nd has  a goo d orie ntatio n o f   the fitness fun c tion to eva l u a te the qu al ity of a te st data. T h is paper i n troduc es  sev e ral ev ol ution  tes t   meth ods, s h o w s its adva n t ages  a nd  pro b le msit  can   e ffectively so lv e, an d  prop o s esan  i m pr ov ed   evol ution a ry te st data gen erat ion  meth od,  w h ich can g e n e ra te better test data.    Ke y w ords :  aut omatic test data gen erati on,  e v oluti on al gor ithm, fitness, fun c tion structural  test         Copy right  ©  2014 In stitu t e o f  Ad van ced  En g i n eerin g and  Scien ce. All  rig h t s reser ve d .       1. Introduc tion  Software te st ing is to  find  defect s  in t he so ftwa r e,it is o ne of th e effective m ean s to  ensure th e software  qualit y, and is an i ndispen sabl e  comp one nt of the softwa r e devel opm ent  life cycle. A  test prog ram  is good or  bad dep end s  on the sele ction of test ca se s. Howe ver,  softwa r e te sti ng is  a  com p licate d  process. It  throug hout the  stag es of  software  develo p me nt  pro c e ss, an d requi re s a lot of manpowe r , material  re sou r ces a nd time. Usu a lly,  test automati o n   techn o logy  can p r ovide  a  method  to g enerate  te st  ca se s  with hi gh q uality, and imp r ove t he  efficien cy of testing. Re sea r ch  a  kind  of  effectiv e test  automation  te chn o logy, to redu ce the  co st  of softwa r e te sting ha s very important si gnifica nce.  Evolutionary  algorith m  ha s be en  appli ed to mai n  f i elds,  su ch  a s   conting ent  power  netwo rk  [1]. Evolutionary Testing m a k e the  test  ca se s ge neration  pro c e ss i n to  method s of u s ing   geneti c  alg o rithm for n u m eri c al o p timization  pr o b lems,  usi n g  the fitness function  a s  test  obje c tives, m appe d te st sp ace  to the   se arch  sp ace  of  the al go rith m, gen erate  test  ca se s  whi c h  meet the target of testing aut omatically and efficient ly. The w hol e pro c e ss  wi thout too mu ch   human i n terv ention, thu s   usin g evoluti onary te stin g  techn o logy t o  gen erate t e st cases  greatly  redu ce s t he t e st  co st .    Evolutionary  testing mai n l y  include s st ructural  evolut ion testing, f unctio nal test ing and   perfo rman ce   testing, et c.  At pre s ent th e mo st wi del y studie d  of  evolutiona ry testing  techno logy  is  stru ctural e v olution te st tech nol o g y. Structu r al  evolu t ion test  ma ke test ta rg et i n to the  cove r  of  the pro g ram  stru cture, su ch as  state m e n t/bran c h  cov e rag e , path coverag e , etc.  [2], the mainly  use d fitness constructo r are  di st an ce o r iented m e tho d , so rting  co ver o r iented   method  and  the  control cove r oriented m e thod [3]. Path orient e d  test data g eneration is  one of the main  method s of  test d a ta g e n e ration  ba se d  on th e  stru ct ural te st. Th e r e a r e  a l o t o f  re sea r che s   for   path ori ented  method, e s peci a lly on e v olutionar y a l gorithm to  g enerate test  data got g r e a t  r e sear ch pr ogr e s s .   Evolution test  has th e adv antage s of ef ficien t, dyna mic an d st ron g  guid a n c e; the key is  to design a reasona ble fitness func tio n .  If the fitness function is  n o t suitable, test efficiency  may  be lower tha n  ran dom te sting. Fo r different a ppli c a t ions o r  test  obje c ts, fitne ss fu nction s  are  different. And in order to  get the bes t effec t,fi tnes s   func tions  need to  be c o nstantly adjus ted   according to t he processin g  of  evolution a ry testing.Th ere a r e tw o main problem s existing i n  the   curre n t evolutionary testin g: the first one is  invalid  solution p r o b lem, whi c h  can't dete r mi ne  wheth e r the  solutio n  is u s ed in th e e ffective  sea r ch do main; t he othe r is t he problem  of  popul ation d e g rad a tion.Th ere  are only  a  few  gen otypes  i n  the  pop ulation,  which  dire cts the l o cal  optimal soluti on can al way s  survive [4]. The mai n ly  re aso n  is th e fitness fun c tion  only acco rdi ng  to wh ethe r it  meet the  test  co ndition s  or is  clo s e  to t he o p timal j u dgment,  rath er th an to  jud ge  Evaluation Warning : The document was created with Spire.PDF for Python.
    ISSN: 2302-4 046   TELKOM NIKA   TELKOM NIKA  Vol. 12, No . 1, Janua ry 2014:  818 – 8 2 2   819   wheth e r th e  solutio n  i s  in  the effective  sea r ch  d o mai n , wh ether it  lead s to th e f a ctors  su ch   as  degradatio n o f  population o r  not.  In addition, th e evolution a ry testing al go rithms   mo stly use  covera g e  [5] the indi cators a s   the feedb ack  informatio n of  testing p r o c e dure s , te st  executio n is  not  con s id ere d  i n  co st, there i s   no gu ara n te e that you g e t the test p r og ram  set  o f  execution  efficien cy. For a  software, if  compl e tes all  the  req u ired  validation  works ne ed  a l o t of te sting  pro c ed ures,  and  ho wever th e   test executio n efficien cy i s  lo w, thu s  can g r eatly le ngthen th e te st time, and  l e ssen  efficie n cy.  And in th e  software  devel opment  cycl e ,  need  for  re gre ssi on te sti ng for many  times, repe ated  low exe c utio n efficien cy o f  testing p r o c ess, w ill  se ri ously affe ct the p r oje c t schedul e. To  solve   these  pro b le ms, this p a p e r imp r oved  the adapt ive  fitness fu nction of an in tegrated  de si gn  approa ch, bo th to ensure coverage, im prove the  ex ecutio n effici ency, and  ca n effectively avoid   popul ation de grad ation an d  local optimal  solutio n  of the probl em.       2. Impro v ing  the Fitne ss  Function   For invalid  solution a nd popul ation deg rad a tion pro b lem s , resea r ch ers p u t  forwa r d ano ptimization   met hod ba sed  on  p uni shme n tfunction  of evolutiona ry  testing [6], t h is  method ca n   puni sh po pulation  i ndi viduals wh i c h areout side  ofthe sea r ch  domai n, and  redu ce sthe  fitness value   of local  opti m al solu tion,  make mo re  solutio n s in volve in the  next  iteration ofev olution proce ss.  Th e fitness functio n  is d e fined a s  sh o w n in form ula  (1):       y x f x   θ g x   θ h x ,   θ , θ ∈ 0, ∞  (1)     In formula (1 ), f (x) is the original d e finiti on of fitness fun c tion, g ( x) is the pu n i shme nt  function to d eal with inva lid solution s,   θ 1  is invalid solution pu nish pa ram e ter, h(x) is the  puni shme nt functio n  to de al with lo cal  optimal  soluti ons,  θ 2  i s  the  local  optimal  solutio npu ni sh   para m eter.  θ 1  and  θ 2  is consta nt which sco pe is [0, + ∞ ), th eir values d e termin es th e  corre s p ondin g  penaltie s , and is ne ede d to be deter mined befo r e  the test started. For inval i d  solutio n s a n d  local o p timal  solution s, u s ing st ati c  met hod an d dyn a mic p uni sh ment metho d  to   dopu nishmen t, becau se f o r invalid  so lutions,effe ctive input do main of solution ha s b een   determi ned be fore th e  start   of the te st, to  judg e  wheth e r th ey a r e v a lid o n ly  nee d  to  acco rdin g  to   distan ce of th e solutio n  to the effective input fi elds. T he greater of  the distan ce,  the large r  ofthe  puni shme nt functio n ’s valu e, for efficient  solutio n s, th e puni shm ent  function  doe s not  work. T he  puni shme nt for local optimal solutio n s is requi red  t o  according t o  the individu al’s propo rtio n o f   the pop ulatio n to dynami c ally adju s tme n t. Usu a lly  u s e sim u lated  a nneali ng p uni shme nt fun c tion   or ad aptive p unishment fu nction t w o  wa ys to puni sh  l o cal  optimal  solution. The l onge r ofthe ti me  individual a s  l o cal  optimal  solutio n , the l a rge r  of  the  p unishment fu nction’ s valu e .  So, the fitness  function  can  dynamic a d j ustment of the individu al fitness valu e acco rding  to whethe r the   individual i s  the efficient solution or l o cal optimal sol u tion, avoidin v alid solutio n  and deg ra da tion   occurre d .  For evolution a ry  al gorithm   usi ng cove rage  i ndi cators a s  judg me nt of te st progra m ’ s   optimizatio n goal, and lea d  to the probl em of low  efficien cy, resea r ch er p r op osed test pro g ram  gene ration  m e thod b a sed  on multiple  target optim ization s  [7]. The meth od  con s i s ts of t w o  obje c tive functions: the first  one i s  to a c h i eve te st p r o c edure’s l a rge s t cove ra ge; the second i s   to   redu ce  test  e x ecution  cost  to a  minimu m.In te st p r o g ram  ge neration p r obl em s, for  cove rag e  is  the main indi catorfo r  a s se ssi ng ho w th e test pro g ra m is. Ho weve r, for a test p r og ram with v e ry  low  cov e rag e ,  while it s ex e c ut ion  co st  i s  v e ry  sm a ll, e x ecution  effici ency i s  hi gh,  but it is  not the   solutio n  we n eed. If not remove those  solutio n s ,they  will always  at the top for they have high   executio n efficien cy. So we need to  set  punishme nt  function to eli m inate the solution of sm all  coverage. We  can u s e form ula (2 ) to determin e  wh eth e r a sol u tion  sho u ld be eli m inated:     y x           100%  (2)     In formula (2), f ma x   and f min   is the  maxim u m an d mi ni mum valu e of  cove rag e  in d i viduals  allow in a  p opulatio n. Th e form ula  re flects th e p o pulation  indiv i dual s’ deviat i on d egree  of  minimum coverage rate relative to the ma ximum value.If the deviation degree exc e eds  t h e   Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 2302-4 046                          Study oftest d a ta gene ratio n  m e thod based on e v oluti onary alg o rith m   (Zhang Yu nlong )  820 threshold   wh ich i s  set at  the  begin n i ng of  test, t he in dividual s  will b e   reg a rde d   as inv a lid   solutio n , and  can b e  elimin ated.  In addition, t hetraditio nal  evolutiona ry test  data  ge n e ration  meth od exist s  p r o b lems of  algorith m  co mplex, and coding difficult ies and p a ra meters are n o t easy to se t up and so  on,  some  schol ars put fo rwa r d  a kin d  ofsoftware  test d a ta automate d   gene ration  m e thod b a sed  on  differential ev olution alg o rit h m [8]. Operator to  the o peratio n of the algo rithm  was im prov ed,  solve s  the problem of test  data  to generate di scret e  differential  evolution alg o rithm. The b a si c   idea of  differential evoluti on alg o rithm   is firstgen erat e an i n itial po pulation i n  th e se arch  sp a c e,  then produ ce ne w indivi dual by weig hting any tw o individual s’  vector diffe rential a nd t hen  sup e rim p o s e  a third indivi dual. The n  compa r e the fi tness value  of the new in dividual an d the  individual, if the new in dividual’ s  fitness  value is  bette r than that of the pare n t individual’s fitn ess  value, then  repla c e  pare n t individual  with the  n e w in dividual , or pa rent i ndividual i s   still  pre s e r ved. By iterative calcul ation un cea s in gly, keep excellen t  individuals surviving,  and   eliminate inf e rio r  individu als, thu s  the  sea r ch p r o c ess was  gui ded to a ppro a ch th e opti m al  s o lution.  Acco rdi ng to  the mention e d  evolutiona ry te sting tech nology imp r o v ement idea,  we put  forwa r d th e followin g  met hod to  con s truct of fitness  function: Fi rst  of all, in ord e r  to mea s u r e  the  quality of the test program , in addition to using  co verage indi cato rs, at the same time also u s e  perfo rman ce  indicators an d dista n ce in dicato rs.  Exe c ution  efficie n cy indi cato rs can g uaran tee  test sp eed of  test prog ram  in large  soft ware, and g u a rante e  the test ca se s to  cover th e cu rrent  node o r  state m ents to the  test set go als at the  begin n ing of dista n c e info rmatio n, and judg e  the   curre n t nod e’ s o r  a  state m ent’s  dista n ce  inform ation  with test  goal while  covering  the t e st   ca se.Th r ee  i ndicators  evaluatea  test   prog ram  at t he  sam e  tim e , whi c h  can  assu re  the  high  coverage  rate of  evolutio nary te sting.I n  ad diti on, in  order to  sol v e the  pro b le m of p opul ation   degradatio n and lo cal opti m al solutio n , the introdu cti on of puni sh ment functio n  and the fitness  function to  in fluence po pu lation evoluti on test  ca se s a r e eli m ina t ed. The fitn ess fun c tion  as  sho w n in formula (3 ):    y x f x θ e x θ d x θ g x θ h x   θ , θ , θ , θ  ∈ 0 , ∞   (3)     The f(x) is th e origin al fitness functio n , e(x)  is the ex ecutio n effici ency of the d e ci sion   function, d ( x) is the test  case s to  cover the di stan ce  with the targ et node fun c t i ons, g ( x) is t he  puni shme nt for invali d  sol u tion fun c tion , h(x) i s  th e lo cal  optimal  solution  of the  penalty fun c ti on,   θ 1 ,  θ 2 ,  θ 3 ,  θ 4  is the fou r  rel e vant param et ers  of the functio n s, the y  ar e setu p b e fore the  start of  the test. The value of the four parame t ers det e r min e s thefun ctio ns’ influen ce  degre e  oftest   ca se s.       3. Experimental Verifica tion  In orde r to ve rify the validity of the desi gn  of  fitness function,  the triangle pro g ram  test  experim ent was  ca rrie d  o u t. Take  the th ree si de s of th e trian g le a,  b ,  c a s  for the i nput item s, th e   test goal i s  to  achieve th re e side s e qual  node s, t hat is a = b = c. Rep r ese n tation for the evolution  of  popul ation in dividual s is (a, b, c). The  experim ent  o f  the total number of evol ution T=500,  the  size of the po pulation  size P=200, the la rge s t numb e r of iterations I =  20. The in p u t fields for th e  input item a,  b, c i s  [30, 5 0 ]. For the  efficien cy  of de cisi on fun c tio n  e(x) u s ing  comp uter  clo ck  cycle s  to  det ermin e , the compute r 's m a in fre quen cy  for exe c utin g the te st progra m  is1.7G Hz.  Therefore  ex 1 . 7 T I /1.7 , distan ce functi on  dx m in |30 x|, | 50 x | , punishm ent  function of in effective solut i on  gx 1 / 0. 001 1 /dx , punishm ent function o f  local optima l   solut i o n    hx  e xp  2/ T   P ,  θ 1 ,  θ 2 ,  θ 3 ,  θ 4  are  set to 0.5, 1,  0.5, 30. So th e fitness fun c tion  y(x) as sho w n in the formu l a (5):     y x f x 0 . 5  1 . 7 T I 1.7 m i n | 30 x | , | 50 x | 0 . 5   1/0 . 001 1 / dx 3 0 e xp   2/ T   P  (5)     In experim en t, each  different si ze  of the  po pulatio n wa s  se parately run fo r  10 time s,  record ea ch  time to find the optimal  solution of the  iteration n u mber  and  ru nning time, a nd  Evaluation Warning : The document was created with Spire.PDF for Python.
    ISSN: 2302-4 046   TELKOM NIKA   TELKOM NIKA  Vol. 12, No . 1, Janua ry 2014:  818 – 8 2 2   821   cal c ulate th e  avera ge ite r ativ e count  and ite r ation  time. Figure 1 an d fig u re  2 sho w   the   experim ental results comp arison  to  f(x) and  y(x).   From th e exp e rime ntal re sults of figure  1 and fi g u re  2 ,  it can be  se en that after  usin g the  adaptive valu e fun c tion y(x ) , the tri angle   prog ram   hav e obviou s  i m prove  both ite r ation  co unt a nd  iteration time,  whi c h in dica tes after  add ed the p uni shment fun c tio n  and  efficien cy functio n , y(x)  is ve ry efficie n t to imp r ove  the  cove rag e  an d p uni sh ment ineffe cti v e sol u tion s  and l o cal o p timal  s o lution.        Figure 1. Gen e rate an e quil a teral tria ngle  of the iteration cou n t          Figure 2. Gen e rate an e quil a teral tria ngle  of the iteration time      4. Summar y     In this pap er,  the method o f  adopting a d d s a  se ri es  of control mea n s  on the b a si s of the  origin al fitness functio n  to solve the p r o b lems  of evolutionary te sting. And su pe rvise the p r o c ess  of populatio n  evolution, b o th retain ed the ev olution a r y test cove rage, and  ca n  guarantee t e s t   prog ram’ s ex ecutio n effici ency, a n d  can al so  avoi d de gradatio n an d i n valid  sol u tion  in t he  pro c e ss of po pulation evol ution, optimize t he quality and efficie n cy  of test data generation.     100 12 0 140 16 0 180 20 0 0 2 4 6 8 10 12 14 16 18 Po p u la tio n  S i z e I t e r a t e  C ount C o mmon F i tne s s   F u n c t i on O p ti mi z e d  F i t n e s s  F unc ti on 10 0 12 0 14 0 16 0 18 0 20 0 6 8 10 12 14 16 18 P o p u la tio n  S i z e I t er at e  T i m e ( m s ) C o m m o n  Fi t n e s s   Fu n c t i o n Op t i m i zed  F i t n es s   F u n c t i o n Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 2302-4 046                          Study oftest d a ta gene ratio n  m e thod based on e v oluti onary alg o rith m   (Zhang Yu nlong )  822 Referen ces   [1]    Sa w a n Sen, Pri y ank a Ro y, Abhi jit Chakr a varti,  Samarjit  Sengu pta. Genet ator C ontr i buti on Base d   Con gestio n  Ma nag ement us in g Mult io bjectiv e  Genetic Al go rithm.  T E LKOMNIKA Indon e s ian Jo urn a l of   Electrical E ngi neer ing . 2 011;  9(1): 1-8.   [2]    Sand ip C h a n da a nd Ab hi nan da n De.  Con gestio n  R e lief  of Conti nge nt Po w e r  Net w ork  w i t h   Evoluti onar y Optimizatio n   Algorit hm.  T E LKOMNIKA Indones ian Jo urn a l of  Electrical  Engin eeri n g .  201 2; 10(1): 1- 8.  [3]   XIE  Xia o y u an.   Surve y   of E v oluti onar y T e sting.  Jour nal  of F r ontiers  of  Co mp uter  Scienc e an d   T e chno logy . 2 008, 2(5):4 49- 466.   [4]    Shi Li ang. R e s earch o n  T e st  Data Automati c Generatio n. Nanj in g: S outh east Univ ersit y , 2007.   [5]    Z hang Li ang. Cover age  M a t r ix bas ed  Ev o l utio nar y T e st Program Ge nerati on for M i croproc esso r   Verification.  Jo urna l of Co mp uter- Aide d De sign & Co mput er Graphics . 2 011; 23( 3): 456 -462.   [6]    Z hang  Na n. R e searc h  o n  Ev oluti onar y T e sting Optim i zatio n Base d o n  Pe nalt y  F uncti on.   Co mp uter &   D i g i t al  En gi ne eri n g . 20 09; 37( 4): 1-3.  [7]    Z hang  Li an g.  T e st Program  Generati o n  Ba s ed  on  Multi- o b jectiv e Evo l uti onar y  Alg o rith m.  Journ a l of   F r ontiers of Co mp uter Scie nc e and T e ch no l ogy . 201 0; 22( 8): 1382- 13 89.   [8]    Hua ng  Xia o ch eng. App licati o n of modifie d   differenti a l evo l utio n in  test data gen erati o n .   Journal o f   Co mp uter Appl icatio ns . 200 9; 29(6): 17 22- 17 54.   Evaluation Warning : The document was created with Spire.PDF for Python.