只有在多线程时才会抛出 StackOverFlowException 异常

Question

我正在编写一个程序，以帮助我收集有关密码安全的研究报告的统计数据。我决定在尝试暴力破解MD5哈希密码时使应用程序运行在多个线程上，以获得明显的性能提升。该应用程序在单个线程上运行良好，但是一旦有2个线程运行，TryPass函数中的"using (MD5 md5Hash = MD5.Create())"就会抛出StackOverFlowException异常。

    // Microsoft's GetMd5Hash function.
    static string GetMd5Hash(MD5 md5Hash, string input)
    {
        // Convert the input string to a byte array and compute the hash. 
        byte[] data = md5Hash.ComputeHash(Encoding.UTF8.GetBytes(input));

        // Create a new Stringbuilder to collect the bytes 
        // and create a string.
        StringBuilder sBuilder = new StringBuilder();

        // Loop through each byte of the hashed data  
        // and format each one as a hexadecimal string. 
        for (int i = 0; i < data.Length; i++)
        {
            sBuilder.Append(data[i].ToString("x2"));
        }

        // Return the hexadecimal string. 
        return sBuilder.ToString();
    }

    static bool TryPass(string attempt, string password)
    {
        using (MD5 md5Hash = MD5.Create())
        {
            if (GetMd5Hash(md5Hash, attempt) == password)
                return true;
            else
                return false;
        }
    }



    static bool BruteForce(BruteOptions bruteOptions)
    {
        if (bruteOptions.prefix.Length == 1 && TryPass(bruteOptions.prefix, bruteOptions.password)) // If it's the first in a series, try it.
            return true;

        for (int i = 0; i < bruteOptions.chars.Length; i++)
        {
            if (TryPass(bruteOptions.prefix + bruteOptions.chars[i], bruteOptions.password))
            {
                Console.WriteLine("The password is: " + bruteOptions.prefix + bruteOptions.chars[i]);
                return true;
            }

            if (bruteOptions.prefix.Length + 1 < bruteOptions.maxLength)
                if (BruteForce(bruteOptions))
                    return true;

            //Console.WriteLine(prefix + chars[i]);
        }

        return false;
    }



    public struct BruteOptions
    {
        public string password, prefix;
        public char[] chars;
        public int maxLength;
    }

    static void OptionBruteForce()
    {
        Console.WriteLine("-----------------------");
        Console.WriteLine("----- Brute-Force -----");
        Console.WriteLine("-----------------------");

        BruteOptions bruteOptions = new BruteOptions();
        bruteOptions.password = ReadString("Enter the MD5 password hash to brute-force: ");
        bruteOptions.chars = ReadString("Enter the characters to use: ").ToCharArray();
        bruteOptions.maxLength = ReadIntegerRange("Max length of password: ", 1, 16);
        bruteOptions.prefix = "";

        Stopwatch myStopWatch = Stopwatch.StartNew();

        int NUM_THREADS = bruteOptions.chars.Length;
        Thread[] workers = new Thread[NUM_THREADS]; // Run a thread for each char.
        var countdownEvent = new CountdownEvent(NUM_THREADS);
        bool result = false;

        // Start workers.
        for (int i = 0; i < NUM_THREADS; i++)
        {
            int index = i;
            BruteOptions newBruteOptions = bruteOptions;
            newBruteOptions.prefix = bruteOptions.chars[index].ToString();

            workers[index] = new Thread(delegate()
            {
                // Also check single char.
                if (BruteForce(bruteOptions))
                {
                    result = true;

                    // End all other threads.
                    for (int ii = 0; ii < NUM_THREADS; ii++)
                    {
                        if (workers[ii].ThreadState == System.Threading.ThreadState.Running && index != ii) // Ensures we don't prematurely abort this thread.
                        {
                            workers[ii].Abort();
                            countdownEvent.Signal(); // Signal so we can zero it and continue on the UI thread.
                        }
                    }
                }

                // Signal the CountdownEvent.
                countdownEvent.Signal();
            });

            workers[index].Start();
        }

        // Wait for workers.
        countdownEvent.Wait();

        if (!result)
            Console.WriteLine("No Match.");

        Console.WriteLine("Took " + myStopWatch.ElapsedMilliseconds + " Milliseconds");
    }

这就是所有相关的代码了。非常希望能得到关于为什么会出现这种情况的见解！我完全被难住了。我尝试在初始化每个线程时指定更大的堆栈大小，但没有效果。

提前感谢！

- Shane Reeves

Answer 1

您的static bool BruteForce(BruteOptions bruteOptions)函数存在无限递归：如果长度允许，它会使用相同的参数再次调用自身：

if (bruteOptions.prefix.Length + 1 < bruteOptions.maxLength)
    if (BruteForce(bruteOptions))

bruteOptions 在函数进入时保持不变。

作为解决方案，您可以使用以下代码：

if (bruteOptions.prefix.Length + 1 < bruteOptions.maxLength)
{
    BruteOptions newOptions = bruteOptions;
    newOptions.prefix += bruteOptions.chars[i];
    if (BruteForce(newOptions))
        return true;
}

此外，在主函数中使用的委托中，传递给它的应该是bruteOptions而不是newBruteOptions。因此，您的多线程并没有被使用。所有线程都在测试相同的密码。请将其更改为newBruteOptions。

另外，不要假设任何关于线程执行顺序的事情。您假设所有的工作线程都被填充，直到有一个找到正确的密码，这可能是错误的。在这一行中，您会得到一个NullReferenceException异常：

if (workers[ii].ThreadState == System.Threading.ThreadState.Running && index != ii) // Ensures we don't prematurely abort this thread.

- Aneri

---

我简直不敢相信我错过了那个！非常感谢您的帮助，非常感谢您，先生！运作得像魔法一样。 - Shane Reeves

Answer 2

仅供娱乐，这里有一个不使用递归实现的替代方案，并更好地利用了 .Net 的语言结构和框架。

class Program
{
    private static string StringFromIndexPermutation(char[] characters, int[] indexes)
    {
        var buffer = new char[indexes.Length];
        for (var i = 0; i < buffer.Length; ++i)
        {
            buffer[i] = characters[indexes[i]];
        }

        return new string(buffer);
    }

    /// <summary>
    /// Increments a set of "digits" in a base "numberBase" number with the MSD at position 0
    /// </summary>
    /// <param name="buffer">The buffer of integers representing the numeric string</param>
    /// <param name="numberBase">The base to treat the digits of the number as</param>
    /// <returns>false if the number in the buffer has just overflowed, true otherwise</returns>
    private static bool Increment(int[] buffer, int numberBase)
    {
        for (var i = buffer.Length - 1; i >= 0; --i)
        {
            if ((buffer[i] + 1) < numberBase)
            {
                ++buffer[i];
                return true;
            }

            buffer[i] = 0;
        }

        return false;
    }

    /// <summary>
    /// Calculate all the permutations of some set of characters in a string from length 1 to maxLength
    /// </summary>
    /// <param name="characters">The characters to permute</param>
    /// <param name="maxLength">The maximum length of the permuted string</param>
    /// <returns>The set of all permutations</returns>
    public static IEnumerable<string> Permute(char[] characters, int maxLength)
    {
        for (var i = 0; i < maxLength; ++i)
        {
            var permutation = new int[i + 1];
            yield return StringFromIndexPermutation(characters, permutation);

            while (Increment(permutation, characters.Length))
            {
                yield return StringFromIndexPermutation(characters, permutation);
            }
        }
    }

    static string ReadString(string message)
    {
        Console.Write(message);
        return Console.ReadLine();
    }

    private static int ReadIntegerRange(string message, int min, int max)
    {
        Console.Write(message + "({0} - {1})", min, max);

        while(true)
        {
            var test = Console.ReadLine();
            int value;

            if (int.TryParse(test, out value))
            {
                return value;
            }
        }

        return -1;
    }

    static void OptionBruteForce()
    {
        Console.WriteLine("-----------------------");
        Console.WriteLine("----- Brute-Force -----");
        Console.WriteLine("-----------------------");

        var password = ReadString("Enter the MD5 password hash to brute-force: ");
        var chars = ReadString("Enter the characters to use: ").Distinct().ToArray();
        var maxLength = ReadIntegerRange("Max length of password: ", 1, 16);

        var myStopWatch = Stopwatch.StartNew();

        var result = false;
        string match = null;
        var cancellationTokenSource = new CancellationTokenSource();
        var passwordBytes = Encoding.Default.GetBytes(password);
        var originalMd5 = MD5.Create();
        var passwordHash = originalMd5.ComputeHash(passwordBytes);
        var hashAlgGetter = new ConcurrentDictionary<Thread, MD5>();

        try
        {
            Parallel.ForEach(Permute(chars, maxLength), new ParallelOptions
            {
                CancellationToken = cancellationTokenSource.Token
            }, test =>
            {
                var md5 = hashAlgGetter.GetOrAdd(Thread.CurrentThread, t => MD5.Create());
                var data = Encoding.Default.GetBytes(test);
                var hash = md5.ComputeHash(data);

                if (hash.SequenceEqual(passwordHash))
                {
                    myStopWatch.Stop();
                    match = test;
                    result = true;
                    cancellationTokenSource.Cancel();
                }
            });
        }
        catch (OperationCanceledException)
        {
        }

        if (!result)
        {
            Console.WriteLine("No Match.");
        }
        else
        {
            Console.WriteLine("Password is: {0}", match);
        }

        Console.WriteLine("Took " + myStopWatch.ElapsedMilliseconds + " Milliseconds");
    }

    static void Main()
    {
        OptionBruteForce();
        Console.ReadLine();
    }
}

- mlorbetske

---

看起来很棒，做得好！ 如果我将来要重写，我一定会更仔细地研究这个并尝试一下。感谢你的贡献！ - Shane Reeves

Answer 3

我猜你的单线程代码看起来有些不同。

我建议去掉递归。

- zmbq

---

递归对于计算每个可能的密码组合是必要的。除非还有其他方法？ - Shane Reeves

递归总是可以用自定义堆栈的循环来替代。 - Aneri

我该怎么做呢？谢谢！ - Shane Reeves