A method and a system for cleaning malicious software (malware), a computer program product, and a storage medium are provided. A relation graph is established to associate processes in an operating system and related elements. A node marking action is performed on the relation graph when a predetermined condition is satisfied. The node corresponding to a malicious process and its related nodes are marked with a first label. The nodes of other normal processes and their related nodes are marked with a second label. Then, those nodes marked with both the first label and the second label are screened, so that each of the nodes is marked with only the first label or the second label. Finally, the processes and elements corresponding to the nodes marked with the first label are removed.