How can one tell if a binary is safe to give sudo permissions for to an untrusted user?

In general, it's impossible to know for sure - even a seemlingly-perfectly-safe program could have vulnerabilities that mean it can be used for arbitrary actions - but here are some things to check for:

Does the program do any of the following?

• Reveal the contents of arbitrary files or devices.
• Copy, move, write, or delete arbitrary files.
• Set / modify arbitrary environment variables (that will be picked up by other privileged processes), or make arbitrary changes to specific ones.
• Invoke IOCTLs or otherwise interact with arbitrary devices.
• Change ownership or permissions on arbitrary files.
• Mount arbitrary file systems, or change mount options on existing ones.
• Allow direct access to the memory of the system or of an arbitrary process (such as a debugger).
• Allow launching arbitrary programs.

Any program that does any of those is not safe to grant a low-privileged user sudo access to. This rules out, for example, any program with the ability to specify an output file (usually via a -o or -f parameter), process an input file in any way that reveals its contents (even just via a sufficiently-informative error message about the input format being wrong), and the vast majority of script runtimes (including shells).

If you replace arbitrary in those checks with limited or specific, then you've kicked the problem down a step (or several): do any of the things that the program can do lead to such arbitrary happenings, possibly through multiple levels of indirection? For example, if your program allows the user to set a unique environment variable, that will cause a privileged program to read a different file than expected, and that different file will cause the system to allow users to mount an image file of their choice as a file system with the setuid bit respected, then you must not allow untrusted users to run that program.

However, just because a program passes all of these checks still doesn't mean it's actually safe. For example, if it performs certain network actions (such as listening on restricted ports or sending raw packets), it may be unsafe because there might be another program on the network (or on the same machine) assuming that every process capable of doing such things is owned by a trusted user - after all, those actions require root - and you've broken that assumption. Furthermore, the list of bullet points above is just stuff I thought of in a few minutes; there are almost certainly some avenues to privilege escalation that I didn't include.

Finally, as with all security questions, it depends on your threat model.

• Is the attacker (untrusted user) local to the machine with physical access, or are they remote? It's extremely difficult to prevent a determined attacker with physical access from getting root, especially if they need to be able to (re)boot the machine without assistance, so consider what risks you're willing to accept.
• Is the machine shared among users? Then you need to consider additional cross-user attacks, such as denial-of-service (by consuming excessive resources or rendering the machine unusable).
• Do you require non-repudiation (the ability to prove who did something)? Then you need to make sure that you can tie any actions done through sudo to the user who did them.
• Do you need to prevent the user from doing some things that even a non-root user usually can do (such as run arbitrary programs in their own user context even if those programs are things like games or cryptominers, or open TCP client connections to arbitrary hosts and ports)? Then you need to additionally consider the means by which you're enforcing this restriction, and prevent running as sudo any programs that might lead to a way for the user to bypass the restriction.

Etc. A truly comprehensive answer is not going to be possible here; it depends on too many things. However, I will say this: it is very hard to ensure an untrusted user, given the ability to run as root any non-trivial program (that was not explicitly designed to be safely run that way), cannot do something unexpected. Even if any one such program doesn't allow anything you find it important to prevent, it might be possible to chain multiple such programs together to achieve the attacker's goal.

It essentially boils down to the halting problem, you can audit the code or reverse engineer the binary, however even if there are no "features" that let you execute arbitrary commands there could still be vulnerabilities in the binary or sudo itself that could lead to arbitrary command execution as root for the enabled users.