I believe the legal/ethical principle in question is due process, and whether that constitutes a natural right (hint: yes). The 4th Amendment protects the right of individuals to be free from searches absent of a warrant, which may only be issued on the principled basis that there is reasonable suspicion that you've committed a crime, or preparing to do so in a way that makes you a threat.
Any law that creates the power for a government to blanket search anyone and everyone they please simply for passing through the border (and in the absence of reasonable suspicion), effectively thus either violates the natural right to due process, or must be premised on the flimsy notion that merely travelling constitutes reasonable suspicion. It would be incredibly difficult to argue with a straight face that the simple act of travel alone constitutes reasonable suspicion that you are a criminal/terrorist. Likewise, even travelling to a so-called "terrorist state" seems flimsy to me, as there are millions of innocent people within these nations, and only a small percentage are engaged in terrorist activities.
In the case of pre-existing intelligence sources implicating a specific individual that they may be closely connected to e.g. ISIS (as your example of someone whose brother is a high ranking official in ISIS), then yes, thought the procedure should be, the evidence constituting reasonable suspicion should be used to obtain some sort of special type of warrant targeting that particular individual, which could then be used when they cross the border.
But, that is quite different from a blanket power to search everyone at the border (e.g. force everyone hand over passwords) ..... the latter would be the equivalent of throwing away the 4th Amendment in the US and simply saying, to hell with it, we can now search everyone's houses "just in case" they might be a terrorist.
Will some terrorists slip through if we restricted such searches to cases with reasonable suspicion and applied due process? Yes, likely. But we don't throw away basic human rights for everyone, to make us slightly safer, do we?