HTE in Practice — QuickMutate

Recently, me and John Hughes have been working on different approaches to do mutation testing on Haskell code. John is co-author of QuickCheck and we thought of making the same tool for automating mutation testing to some extent. I loaded up emacs and here is my first attempt to develop QuickMutate

First, let me start by quoting from Wikipedia on mutation testing: "Mutation testing involves modifying a program’s source code or byte code in small ways." The mutations should not break the execution and therefore the mutated programs should pass the type checking. So, I grabbed a version of HTE available online and installed it with Cabal.

> module Test.QuickMutate where
> import Language.Haskell.THIH.Typecheck.Load
> import Language.Haskell.THIH.Typecheck.Types hiding (Module)
> import Language.Haskell.Exts.FromTHIH
> import Language.Haskell.Exts hiding (Name)
> import Data.List

Since it is needed to mutate and change different parts of the program, I decided to use Uniplate to do the generics.

> import Data.Generics.Uniplate.Data 

Also, it is required to typecheck all of the mutated programs without interruptions, therefore, I used the following hack:

> import Control.DeepSeq
> import System.IO.Unsafe
> import Control.Exception as CE
> tcHSE :: Module -> Maybe String
> tcHSE ast =  unsafePerformIO $ 
>              CE.catch 
>                (let x = show $ tcHSEModuleWithPrelude ast
>                 in deepseq x (return $ Just x))    
>                ((\_ -> return Nothing) 
>                  :: (SomeException  -> IO (Maybe a))) 

For automating mutation testing, we need a database of mutation operators. It can be modeled as a list of pairs of names (quantified).

> type MutationOps = [(QName,QName)]

Therefore, the mutating function takes the database of mutation operators and the program and generates the mutated programs.

> mutate :: MutationOps -> Module -> [Module]

As the first step, I defined the transformations using Uniplate:

> mutateE :: (QName , QName) -> Exp -> Exp      
> mutateE p e = transformBi (mutateQ p) e
> mutateQ :: (QName , QName) -> QName -> QName
> mutateQ (op,op') x 
>  | x == op   = op'
>  | otherwise = x       
> mutate dic m = let 
>    ms'     = [transformBi (mutateE pair) m  | pair <- dic]
>    -- ...

Then, I used HTE to infer the type of the original program and all the mutated programs. Finally, I filtered out mutated programs with bad types, types different from the original type and duplications.

>    -- ...
>    Just ty = tcHSE m
>    ms''    = filter ( \ m'-> Just ty == tcHSE m') ms'
>    in (nub (m : ms'') )

To make it easier to play with the code, I made a front-end that takes string instead of AST.

> mutateStr :: [(String,String)] -> String -> [String]
> mutateStr dic inp = let 
>  ParseOk m = parseModule inp
>  in map prettyPrint $ concat $ map getDecl 
>     $ mutate [(toQn x ,toQn y ) | (x,y) <- dic] m
>  where
>   toQn :: String -> QName 
>   toQn inp = let ParseOk (Var m ) = parseExp inp in m              
>   getDecl :: Module -> [Decl]              
>   getDecl(Module _ _ _ _ _ _ dcs) = dcs

Then I started to test.

Testing if it actually does the mutation where it should:

> test_new =  mutateStr  [("(+)","(-)")]  "f x = x + x" 
ghci> test_new 
  ["f x = x + x","f x = x - x"]

Testing if it accepts a mutation that results in valid, yet different type:

> test_wrong = mutateStr [("(+)","(++)")] "f x = x + x"
ghci> test_wrong 
  ["f x = x + x"]

Testing if it accepts a mutation that does not typecheck:

> test_bad   = mutateStr [("(+)","f")]    "f x = x + x"
ghci> test_bad 
  ["f x = x + x"]

Testing if it removes duplications:

> test_dup   = mutateStr [("(-)","(+)")]  "f x = x + x"
ghci> test_dup 
  ["f x = x + x"]

So far it behaves as expected. Of course, there is much more left to do; this is just the beginning!

About Shayan

Researcher/Programmer at Chalmers University of Technology
This entry was posted in Articles. Bookmark the permalink.

One Response to HTE in Practice — QuickMutate

  1. alex says:

    This is awesome. Thanks. Please upload to github.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s