Computer malware is becoming a serious threat to our daily life in the information-based society. Especially, script malwares has become famous recently, since a wide range of programs supported scripting, the fact that makes such malwares spread easily. Because of viral polymorphism, current malware detection technologies cannot catch up the exponential growth of polymorphic malwares. In this paper, we propose a detection mechanism for script malwares, using dependency graph analysis. Every script malware can be represented by a dependency graph and then the detection can be transformed to the problem finding maximum subgraph isomorphism in that polymorphism still maintains the core of logical structures of malwares. We also present efficient heuristic approaches for maximum subgraph isomorphism, which improve detection accuracy and reduce computational cost. The experimental results of their use in a hybrid GA showed superior detection accuracy against state-of-the-art anti-virus softwares.