diff --git a/bolt/lib/Rewrite/RewriteInstance.cpp b/bolt/lib/Rewrite/RewriteInstance.cpp
--- a/bolt/lib/Rewrite/RewriteInstance.cpp
+++ b/bolt/lib/Rewrite/RewriteInstance.cpp
@@ -4465,6 +4465,14 @@
   std::vector<ELFSymTy> Symbols;
 
   auto getNewSectionIndex = [&](uint32_t OldIndex) {
+    // For dynamic symbol table, the section index could be wrong on the input,
+    // and its value is ignored by the runtime if it's different from
+    // SHN_UNDEF and SHN_ABS.
+    // However, we still need to update dynamic symbol table, so return a
+    // section index, even though the index is broken.
+    if (IsDynSym && OldIndex >= NewSectionIndex.size())
+      return OldIndex;
+
     assert(OldIndex < NewSectionIndex.size() && "section index out of bounds");
     const uint32_t NewIndex = NewSectionIndex[OldIndex];
 
diff --git a/bolt/test/X86/Inputs/broken_dynsym.yaml b/bolt/test/X86/Inputs/broken_dynsym.yaml
new file mode 100644
--- /dev/null
+++ b/bolt/test/X86/Inputs/broken_dynsym.yaml
@@ -0,0 +1,33 @@
+!ELF
+FileHeader:
+  Class: ELFCLASS64
+  Data: ELFDATA2LSB
+  Type: ET_EXEC
+  Machine: EM_X86_64
+ProgramHeaders:
+  - Type: PT_LOAD
+    FirstSec: .a
+    LastSec: .a
+    Align:           0x1000
+Sections:
+  - Name: .a
+    Type: SHT_PROGBITS
+    Content: 00
+    AddressAlign:    0x1
+  - Name: .b
+    Type: 0
+    AddressAlign:    0x1
+  - Name: .bss
+    Type: 0
+    AddressAlign:    0x1
+  - Type: SectionHeaderTable
+    Sections:
+      - Name: .dynsym
+      - Name: .dynstr
+      - Name: .a
+      - Name: .b
+      - Name: .bss
+      - Name: .strtab
+      - Name: .shstrtab
+DynamicSymbols:
+  - Section: .bss
diff --git a/bolt/test/X86/broken_dynsym.test b/bolt/test/X86/broken_dynsym.test
new file mode 100644
--- /dev/null
+++ b/bolt/test/X86/broken_dynsym.test
@@ -0,0 +1,8 @@
+# This test checks if BOLT can process stripped binaries, where symbol's section
+# header index is corrupted due to strip tool.
+
+# RUN: yaml2obj %p/Inputs/broken_dynsym.yaml -o %t
+# RUN: llvm-strip -s %t
+# RUN: llvm-bolt %t -o %t.bolt | FileCheck %s
+
+# CHECK-NOT: section index out of bounds